Sort List, Insertion Sort List, Reverse Linked List, Palindrome Linked List, Delete Node in a Linked List, Remove Linked List Elements, Intersection of Two Linked Lists, Reorder List, Copy List with Random Pointer

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Solution

• Merge sort: use merge two sorted list as helper function.
• Corner case: if only one node left, just return the head to be merged

public static ListNode mergetwosortedlist(ListNode a, ListNode b){
		ListNode head = new ListNode(0);
		ListNode h=head;
		while(a!= null && b!=null){
			if(a.val>b.val){
				h.next=b;
				b=b.next;
			}
			else{
				h.next=a;
				a=a.next;
			}
			h=h.next;
		}
		if(a==null) h.next=b;
		else h.next=a;
		return head;
	}

	public ListNode sortList(ListNode head) {
		if(head==null || head.next==null) return head;
		ListNode fast=head;
		ListNode slow=head;
		while(fast.next!=null &&  fast.next.next!=null){
			fast=fast.next.next;
			slow=slow.next;
		}
		fast=slow.next;//fast now points to mid
		slow.next=null;
		slow=sortList(head);//sort first half
		fast=sortList(fast);//sort second half
		return mergetwosortedlist(slow, fast);    
	}

---

Insertion Sort List

Sort a linked list using insertion sort.

Solution

public ListNode insertionSortList(ListNode head) {
    ListNode pre=head, cur=head, post=head;
    if(head==null ||  head.next==null) return head;
    ListNode dummyhead=new ListNode(0);
    while(cur!=null){
        ListNode tmp=dummyhead;
        while(tmp.next!=null && tmp.next.val<cur.val){
            tmp=tmp.next;
        }
        //now tmp is before the element larger than cur, need to insert cur before
        post=cur.next;
        cur.next=tmp.next;
        tmp.next=cur;
        cur=post;
    }
    return dummyhead.next;
}

---

Reverse Linked List

Reverse a singly linked list.
click to show more hints.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?

Iterative Solution

public ListNode reverseList(ListNode head) {
    if(head==null) return head;
    ListNode cur=head, post=head, pre=null;
    while(cur!=null){
        post=cur.next;
        cur.next=pre;
        pre=cur;
        cur=post;
    }
    return pre;
}

Recursive Solution

public ListNode reverseList(ListNode head) {
    if(head==null || head.next==null) return head;
    ListNode post=head.next;
    ListNode subhead=reverseList(post);
    post.next=head;
    head.next=null;
    return subhead;
}

---

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?

Solution o(n) space

public static boolean isPalindrome(ListNode head) {
        if(head==null) return true;
        ListNode slow=head, fast=head;
        Stack<Integer> stk=new Stack<Integer>();
        stk.push(head.val);
        while(fast.next!=null && fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            stk.push(slow.val);
        }
        
        //slow is now at the lower median
        if(fast.next==null && !stk.isEmpty()) stk.pop();//odd number, pop median
        slow=slow.next;
        while(slow!=null){
            if(slow.val!=stk.pop()) return false;
            slow=slow.next;
        }
        return true;
    }

Solution o(1) space

• reverse last half of the list when we reached median, compare each node

public static boolean isPalindrome(ListNode head) {
        if(head==null || head.next==null) return true;
        ListNode slow=head, fast=head;
        while(fast.next!=null && fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //slow is now at the lower median
        slow=slow.next;
        ListNode pre=null, cur=slow, post=cur;
        while(cur!=null){
            post=cur.next;
            cur.next=pre;
            pre=cur;
            cur=post;
        }
        while(head!=null && pre!=null){
            if(head.val!=pre.val) return false;
            head=head.next;
            pre=pre.next;
        }
        return true;
    }

---

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

Solution

public void deleteNode(ListNode node) {
    if(node==null || node.next==null) return; //tails dont matter
    node.val = node.next.val;
    node.next = node.next.next;
}

---

Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.
Example
Given: 1 —> 2 —> 6 —> 3 —> 4 —> 5 —> 6, val = 6
Return: 1 —> 2 —> 3 —> 4 —> 5
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Solution

public ListNode removeElements(ListNode head, int val) {
    ListNode dummyhead=new ListNode(0);
    dummyhead.next=head;
    ListNode cur=dummyhead;
    while(cur!=null && cur.next!=null){
        if(cur.next.val==val){
            cur.next=cur.next.next;
        }
        else cur=cur.next; // use else here because we want to keep checking continuous vals
    }
    return dummyhead.next;
}

---

Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
begin to intersect at node c1.

Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

Solution

• find length of two lists, and skip the longer list until starting from same length

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       int lena=0, lenb=0;
       ListNode cura=headA, curb=headB;
       while(cura!=null){
           cura=cura.next;
           lena++;
       }
       while(curb!=null){
           curb=curb.next;
           lenb++;
       }
       cura=headA;
       curb=headB;
       if(lena>lenb){
           for(int i=0;i<(lena-lenb);i++){
               cura=cura.next;
           }
       }
       else{
            for(int i=0;i<(lenb-lena);i++){
               curb=curb.next;
           }           
       }
       while(cura!=null && curb!=null){
           if(cura.val==curb.val) return cura;
           cura=cura.next;
           curb=curb.next;
       }
       return null;
   }

Cycle Solution

+Two pointer solution (O(n+m) running time, O(1) memory):
Maintain two pointers pA and pB initialized at the head of A and B, respectively. Then let them both traverse through the lists, one node at a time.
When pA reaches the end of a list, then redirect it to the head of B (yes, B, that’s right.); similarly when pB reaches the end of a list, redirect it the head of A.
If at any point pA meets pB, then pA/pB is the intersection node.
To see why the above trick would work, consider the following two lists: A = {1,3,5,7,9,11} and B = {2,4,9,11}, which are intersected at node ‘9’. Since B.length (=4) < A.length (=6), pB would reach the end of the merged list first, because pB traverses exactly 2 nodes less than pA does. By redirecting pB to head A, and pA to head B, we now ask pB to travel exactly 2 more nodes than pA would. So in the second iteration, they are guaranteed to reach the intersection node at the same time.
If two lists have intersection, then their last nodes must be the same one. So when pA/pB reaches the end of a list, record the last element of A/B respectively. If the two last elements are not the same one, then the two lists have no intersections.

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        ListNode pA = headA;
        ListNode pB = headB;
        
        ListNode tailA = null;
        ListNode tailB = null;
        
        while (true) {
            if (pA == null) {
                pA = headB;
            }
            
            if (pB == null) {
                pB = headA;
            }
            
            if (pA.next == null) {
                tailA = pA;
            }
            
            if (pB.next == null) {
                tailB = pB;
            }
            
            //The two links have different tails. So just return null;
            if (tailA != null && tailB != null && tailA != tailB) {
                return null;
            }
            
            if (pA == pB) {
                return pA;
            }
            
            pA = pA.next;
            pB = pB.next;
        }
    }

---

Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes’ values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Solution

• find median, reverse second half, merge two parts

public static void reorderList(ListNode head) {
     if(head==null || head.next==null) return;
     ListNode slow=head, fast=head;
     while(fast.next!=null && fast.next.next!=null){
         fast=fast.next.next;
         slow=slow.next;
     }
     ListNode cur=slow.next, post=cur, pre=null;
     slow.next=null;
     while(cur!=null){
         post=cur.next;
         cur.next=pre;
         pre=cur;
         cur=post;
     }
     while(pre!=null && head!=null){
         post=head.next;
         head.next=pre;
         pre=pre.next;
         head.next.next=post;
         head=post;
     }
 }

---

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.

Recursive Solution

• Java limits recursion stack size to 128k, so I hit stackoverflow, while c++ could pass the OJ…

public RandomListNode copyRandomList(RandomListNode head) {
    if(head==null) return null;
    //copy current node value, next pointer
    if(map.containsKey(head)){
        return map.get(head);
    }
    RandomListNode newhead = new RandomListNode(head.label);
    map.put(head, newhead);
    newhead.next=copyRandomList(head.next);
    //random pointer
    newhead.random=copyRandomList(head.random);
    return newhead;
}

Iterative Solution

• Use a hashmap to keep paris, for copying random pointers

public RandomListNode copyRandomList(RandomListNode head) {
    if(head == null) return null;  
    HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();  
    RandomListNode newhead = new RandomListNode(head.label);  
    map.put(head, newhead);  
    //copy next pointers
    RandomListNode cur = head.next, copylast = newhead; 
    while(cur != null){  
        copylast.next = new RandomListNode(cur.label);  
        map.put(cur, copylast.next);  
        cur = cur.next;
        copylast = copylast.next;
    }  
    cur=head; copylast=newhead;
    while(cur!=null){
        copylast.random = cur.random == null ? null : map.get(cur.random);
        cur=cur.next;
        copylast=copylast.next;
    }
    
    return newhead;  
}