Interview Note - Linked List

1. Introduce Dummy Node

When the head of the target list we want to return may be different from the original given list, we can use a dummy node linked to the result so that we can get what we want by calling dummy.next.

Remove Duplicates from Sorted List II:

public class Solution {
    public static ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        ListNode cur = head;
        int dup = Integer.MIN_VALUE;

        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                dup = cur.val;
                while(cur.val == dup) {
                    cur = cur.next;
                    // if the rest of elements are all the same
                    if(cur == null) {
                        return dummy.next;
                    }
                }
            } else {
                pre.next = cur;
                pre = pre.next;
                cur = cur.next;
                // add null to pre.next: in case the rest of elements are the same and returned above
                pre.next = null;
            }
        }
        // add the last element (since cur.next != null skip this element)
        pre.next = cur;

        return dummy.next;
    }
}

Reverse Linked List II:

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) {
            return head;
        }

        // find the m position node
        int count = 1;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        while(count < m) {
            pre = pre.next;
            count++;
        }

        // do the reverse: pre-> reverse[first->cur->next] ...
        ListNode first = pre.next;
        ListNode cur = pre.next.next;
        while(count < n) {
            ListNode next = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            cur = next;
            count++;
            if(count == n) {
                first.next = next;
            }
        }

        return dummy.next;
    }
}

Similar Problems:
Partition List
Insertion Sort List
Reverse Nodes in k-group
Remove Node in Binary Search Tree
Copy List with Random Pointer
Swap Nodes in pairs

Read More