Leetcode: 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.

Understand the problem:
Since the problem only gives the node to be deleted, it is tricky to solve the problem.

We can duplicate the node to be deleted by copy the node.next val to the node. and remove the node.next. 

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void deleteNode(ListNode node) {
        if (node == null) {
            return;
        }
        
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Leetcode: 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?

Understand the problem:
Since the problem asks for O(n) time and O(1) space, we cannot create additional data structure to store the values. The steps to solve the problem are:
  -- 1. Find the middle of the list. 
  -- 2. Reverse the right half of the list. 
  -- 3. Compare the left half and right half.

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        
        int len = getLength(head);
        
        ListNode mid = findMiddle(head);
        
        ListNode newHead;
        
        if (len % 2 == 0) {
            newHead = mid.next;
            mid.next = null;
        } else {
            ListNode dummyNode = new ListNode(mid.val);
            dummyNode.next = mid.next;
            newHead = dummyNode;
        }
        
        // Step 2: reverse the list
        newHead = reverseList(newHead);
        
        // Step 3: compare the list
        ListNode p = head;
        ListNode q = newHead;
        while (p != null && q != null) {
            if (p.val != q.val) {
                return false;
            }
            
            p = p.next;
            q = q.next;
        }
        
        return true;
    }
    
    private int getLength(ListNode head) {
        ListNode p = head;
        int len = 0;
        
        while (p != null) {
            len++;
            p = p.next;
        }
        
        return len;
    }
    
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

Leetcode: 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:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = head.next;
        
        while (curr != null) {
            curr.next = prev;
            prev = curr;
            curr = next;
            
            if (next != null) {
                next = next.next;
            }
        }
        
        return prev;
    }
}

Recursive solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode next = head.next;
        ListNode newHead = reverseList(next);
        
        next.next = head;
        head.next = null;
        
        return newHead;
    }
}

Update on 11/6/15:
Recursive solution using two pointers:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        return reverseListHelper(null, head);
    }
    
    private ListNode reverseListHelper(ListNode prev, ListNode curr) {
        if (curr == null) {
            return prev;
        }
        
        ListNode newHead = reverseListHelper(curr, curr.next);
        
        curr.next = prev;
        
        return newHead;
    }
}

Leetcode: 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

Understand the problem:
The solution should handle the under cases:
1. If the val is the head, we need a dummy node.
2. If the val to be removed has multiple in consecutive. e.g.
dummy -> 1 -> 2 -> 1 -> 1 -> 1 -> 1 -> null, and val = 1
So we need to iterate over all the elements to be removed until the next non-removed one.
3. If the val to be removed is at the tail. 

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        
        ListNode p = dummy;
        
        while (p != null) {
            if (p.next != null && p.next.val == val) {
                ListNode q = p.next;
                while (q != null && q.val == val) {
                    q = q.next;
                }
                p.next = q;
            }
            p = p.next;
        }
        
        return dummy.next;
    }
}

Leetcode: 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.

Understand the problem:
The key to understand the problem is when two linked lists have intersections, they will start "merging". 

The solution is first to calculate the length of the list. Move the head of the longer list by (lenA - lenB) steps. Then compare each node of the two lists. If equal, the intersection point was found. If reached to the end, means null.

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        int lenA = getListLength(headA);
        int lenB = getListLength(headB);
        
        ListNode pA = headA;
        ListNode pB = headB;
        
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                pA = pA.next;
            }
        } else if (lenA < lenB) {
            for (int i = 0; i < lenB - lenA; i++) {
                pB = pB.next;
            }
        }
        
        while (pA != null && pB != null) {
            if (pA == pB) {
                return pA;
            } 
            pA = pA.next;
            pB = pB.next;
        }
        
        return null;
    }
    
    private int getListLength(ListNode head) {
        int len = 0;
        ListNode p = head;
        
        while (p != null) {
            len++;
            p = p.next;
        }
        
        return len;
    }
}

Leetcode: Insertion Sort List

Sort a linked list using insertion sort.
Understand the problem:
The crux of the problem is to understand what is the insertion sort. Basically, the idea of the insertion sort is for a partially sorted list, say, A[] = {1 3 4 5}, and we wanna insert 2 to the list at an appropriate position. In general, the idea of the insertion sort is for a given point i, we wanna make sure its left noes are well sorted. How to achieve this? compare A[i] with A[i -1], if less, swap. 

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode newHead = new ListNode(Integer.MIN_VALUE);
        ListNode prev = newHead;
        ListNode curr = head;
        
        while (curr != null) {
            prev = newHead;
            ListNode next = curr.next;
            
            while (prev.next != null && prev.next.val < curr.val) {
                prev = prev.next;
            }
            
            curr.next = prev.next;
            prev.next = curr;
            
            curr = next;
        }
        
        return newHead.next;
    }

}

Leetcode: Sort List

Sort a linked list in O(n log n) time using constant space complexity.
Understand the problem:
The problem is very straight-forward. The only requirement is O(n logn) time complexity, so it indicates to use quick sort or merge sort. 

In this question we choose the merge sort because quick sort requires many swap operations, which are relatively complicated in the linked list structure. 

Solution:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // find the middle point
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode leftHead = head;
        ListNode rightHead = slow.next;
        
        slow.next = null;
        
        // recursively merge
        leftHead = sortList(leftHead);
        rightHead = sortList(rightHead);
        
        ListNode mergeHead = merge(leftHead, rightHead);
        
        return mergeHead;
    }
    
    private ListNode merge(ListNode leftHead, ListNode rightHead) {
        ListNode newHead = new ListNode(0);
        ListNode curr = newHead;
        
        while (leftHead != null || rightHead != null) {
            if (leftHead == null) {
                curr.next = rightHead;
                break;
            }
            
            if (rightHead == null) {
                curr.next = leftHead;
                break;
            }
            
            if (leftHead.val <= rightHead.val) {
                curr.next = leftHead;
                leftHead = leftHead.next;
                curr = curr.next;
            } else {
                curr.next = rightHead;
                rightHead = rightHead.next;
                curr = curr.next;
            }
        }
        
        return newHead.next;
    }
}

Summary:
The take-away message for this problem is to be very familiar with common sorting algorithms. 

Leetcode: 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.

Understand the problem:
The crux to understand the problem is the deep copy of the list. If the linked list has only next reference, copying could be quite straight-forward. However, with the existence of random pointer, the new copied linked list has no idea where it should point to, because the node pointed by the random pointer at the old linked list is not the same reference in the new linked list.

Solution:
One straight-forward solution to address this problem is to use a hashed map. The key and value is the old and new node in the linked list. So for the random pointer points to a old node, we can map it to the new node. 

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        
        HashMap<RandomListNode, RandomListNode> hashMap = new HashMap<RandomListNode, RandomListNode>();
        
        RandomListNode p = head;
        RandomListNode newHead = new RandomListNode(head.label);
        RandomListNode q = newHead;
        
        hashMap.put(head, newHead);
        p = p.next;
        
        while (p != null) {
            RandomListNode temp = new RandomListNode(p.label);
            q.next = temp;
            q = temp;
            hashMap.put(p, q);
            
            p = p.next;
        }
        
        p = head;
        q = newHead;
        
        while (p != null) {
            if (p.random != null) {
                q.random = hashMap.get(p.random);
            } else {
                q.random = null;
            }
            p = p.next;
            q = q.next;
        }
        
        return newHead;
    }
}

Discussion:
The solution above has time complexity of O(n) since we iterate the linked twice. It has the space complexity O(n) as well since we used a hash map to store the relations between old and new node.

A better approach:
We can solve the problem with only O(1) space complexity. The solution has three steps. 
1. copy the node and insert new nodes into the old node.
2. copy the new random pointer
3. break down the linked list and recover the old linked list

Code (Java):

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        
        // step 1: copy node and insert behind
        RandomListNode p = head;
        while (p != null) {
            RandomListNode copy = new RandomListNode(p.label);
            RandomListNode nextNode = p.next;
            p.next = copy;
            copy.next = nextNode;
            p = nextNode;
        }
        
        // step 2: copy random pointers
        p = head;
        while (p != null) {
            RandomListNode nextNode = p.next.next;
            if (p.random != null) {
                p.next.random = p.random.next;
            } else {
                p.next.random = null;
            }
            
            p = nextNode;
        }
        
        // step 3: break down the linked list and recover the original and new linked list
        p = head;
        RandomListNode newHead = p.next;
        
        while (p != null) {
            RandomListNode q = p.next;
            p.next = q.next;
            if (q.next != null) {
                q.next = p.next.next;
            }
            
            p = p.next;
        }
        
        return newHead;
        
    }
}

Leetcode: Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Understand the problem:
The problem asks for reversing a linked list from position m to n. Note that 1 <= m <= n <= length. The problem also requires for in-place and one-pass traversal of the linked list. 

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        head = dummyNode;
        
        ListNode prev = dummyNode;
        ListNode start = dummyNode.next;
        ListNode end = dummyNode.next;
        
        // move end pointer n - m steps ahead;
        for (int i = 0; i < n - m; i++) {
            end = end.next;
        }
        
        // move all the three pointers to m - 1 steps
        for (int i = 0; i < m - 1; i++) {
            prev = prev.next;
            start = start.next;
            end = end.next;
        }
        
        ListNode nextNode = end.next;
        end.next = null;
        
        // Reverse linked list from start to end
        ListNode newHead = reverseList(start);
        
        prev.next = newHead;
                
        start.next = nextNode;
        
        return dummyNode.next;
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr= head;
        
        while (curr != null) {
            ListNode nextNode = curr.next;
            
            curr.next = prev;
            prev = curr;
            
            curr = nextNode;
        }
        
        return prev;
    }
}

Update 10/8/14:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next  = head;
        
        int count = 1;
        /// Find the tail node of the first segment
        ListNode firstTail = dummyNode;
        while (count < m) {
            firstTail = firstTail.next;
            count++;
        }
        
        /// reverse the middle segement
        ListNode midTail = firstTail.next;
        ListNode midHead = firstTail.next;
        
        ListNode prev = null;
        int num = n - m + 1;
        int i = 0;
        while (i < num) {
            ListNode next = midHead.next;
            midHead.next = prev;
            prev = midHead;
            midHead = next;
            i++;
        }
        
        /// Link with the third segment
        firstTail.next = prev;
        midTail.next = midHead;
        
        return dummyNode.next;
        
    }
}

Leetcode: Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Understand the problem:
The crux of the problem is to understand what is to rotate the list to the right by k places. An easier way to understand the problem is to rotate the tail of the linked list by k places to to the head in counter-clock wise. For e.g. k  = 1,
1->2->3->4->5, becomes 5->1->2->3->4

For k = 2, it becomes 4->5->1->2->3.

So the key of the problem is to find the place where to set the next node as the new head, and linked the old tail to the old head, and break the linked list to the point we are looking for. Note that k could be larger than n since it could be cyclic rotated. 

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null || n == 0) {
            return head;
        }
        
        // get the number of nodes of the linked list
        int len = 0;
        ListNode p = head;
        while (p != null) {
            len++;
            p = p.next;
        }
        
        if (len == 1 || n % len == 0) {
            return head;
        }
        
        int steps = len - n % len - 1;
        
        ListNode newHead = head;
        p = head;
        for (int i = 0; i < steps; i++) {
            p = p.next;
        }
        
        newHead = p.next;
        ListNode q = newHead;
        p.next = null;
        
        while(q.next != null) {
            q = q.next;
        }
        q.next = head;
        
        return newHead;
    }
}

Summary:
The problem itself is relatively simple. When doing linked list questions, be careful about the null pointer exception error.

Update on 9/21/15

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k <= 0) {
            return head;
        }
        
        // Step 1: count the length of the list
        int len = getLengthOfList(head);
        if (k % len == 0) {
            return head;
        }
        
        // Step 2: find the nth element from the end
        int n = k % len + 1;
        ListNode slow = head;
        ListNode fast = head;
        int count = 1;
        
        while (count < n) {
            fast = fast.next;
            count++;
        }
        
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // Step 3: rotate to the head
        ListNode newHead = slow.next;
        slow.next = null;
        fast.next = head;
        
        return newHead;
    }
    
    private int getLengthOfList(ListNode head) {
        int len = 0;
        ListNode p = head;
        while (p != null) {
            len++;
            p = p.next;
        }
        
        return len;
    }
}

Leetcode: Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Understand the problem:
The problem is an extension of last problem, where now k is an input along with the linked list. Again, the solution needs to be in-place and only nodes itself may be changed.

Solution:
The basic idea is to iterate the linked list and increase a counter. If the counter equals to the times of k, we reverse the range of linked list. 

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k == 1)
            return head;
        
        ListNode helper = new ListNode(0);
        helper.next = head;
        
        ListNode pre = helper;
        ListNode cur = head;
        
        int counter = 0;
        
        while (cur != null) {
            counter++;
            
            if (counter % k == 0) {
                pre = reverseRange(pre, cur.next);
                cur = pre.next;
            } else {
                cur = cur.next;
            }
        }
        
        return helper.next;
    }
    
    // Reverse the linked list from pre to end, exclusively
    private ListNode reverseRange(ListNode prev, ListNode end) {
        ListNode head = prev.next;
        ListNode curr = head.next;
        
        while (curr != end) {
            ListNode temp = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            
            curr = temp;
        }
        
        head.next = end;
        return head;
    }
}

Summary:
Take away message from this problem. Reversing the linked list in-place is very basic and important. Make sure you can do it with and without using a dummy head node. 

Update on 9/21/15:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k <= 1) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        
        ListNode prev = dummyNode;
        ListNode curr = head;
        
        int count = 0;
        while (curr != null) {
            count++;
            if (count % k != 0) {
                curr = curr.next;
            } else {
                ListNode next = curr.next;
                
                // Reverse the list
                curr.next = null;
                List<ListNode> result = reverseList(prev.next);
                
                prev.next = result.get(0);
                ListNode tail = result.get(1);
                tail.next = next;
                prev = tail;
                curr = next;
            }
        }
        
        return dummyNode.next;
    }
    
    private List<ListNode> reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode tail = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        List<ListNode> result = new ArrayList<>();
        result.add(prev);
        result.add(tail);
        
        return result;
        
    }
}

Leetcode: Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Understand the problem:
The problem gives a linked list, swap every two adjacent nodes and return its head. For e.g. For 1->2->3->4, swap 1 and 2, 3 and 4, return 2->1->4->3. There are two requirements in the problem: you could only use constant space. You cannot modify the value in the list, just change the nodes. 

Let's take several examples to show the problem.
For a single node list, 1, return 1
For 1->2, return 2->1
For 1->2->3, return 2->1->3.
For 1->2->3->4->5, return 2->1->4->3->5

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode helper = new ListNode(0);
        helper.next = head;
        
        ListNode pre = helper;
        ListNode p = null;
        ListNode q = null;
        ListNode post = head;
        
        while (post != null) {
            p = post;
            q = post.next;
            if (q == null) break;
            
            post = post.next.next;
            pre.next = q;
            q.next = p;
            p.next = post;
            
            pre = p;
        }
        
        return helper.next;
    }
}

A Neat Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode helper = new ListNode(0);
        helper.next = head;
        
        ListNode pre = helper;
        ListNode cur = pre.next;
        
        while (cur != null && cur.next != null) {
            pre.next = cur.next;
            cur.next = cur.next.next;
            pre.next.next = cur;
            
            pre = cur;
            cur = pre.next;
        }
        
        return helper.next;
    }
}

Update on 9/21/15:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        
        ListNode prev = dummyNode;
        ListNode curr = head;
        
        int count = 0;
        
        while (curr != null) {
            count++;
            if (count % 2 == 1) {
                curr = curr.next;
            } else {
                ListNode next = curr.next;
                curr.next = prev.next;
                prev.next.next = next;
                prev.next = curr;
                
                prev = curr.next;
                curr = next;
            }
        }
        
        return dummyNode.next;
    }
}

Leetcode: Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Understand the problem:
This is a classical two-pointer problem of linked list. One thing needs to handle is deleting the head node. 

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || head.next == null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        
        // move fast pointer n steps ahead of slow
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        
        // move slow and fast pointer one step a time
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // delete the node
        if (fast == null) {
            head = head.next;
        } else {
            slow.next = slow.next.next;
        }
        return head;
    }
}

Summary:
This is an easy question. However, when deal with linked list problem, make sure you cover all the corner cases. 

Leetcode: Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

click to show hints.

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

Understand the problem:
The problem asks for flattening a binary tree to a linked list in-place. Given the example shown above, it is actually a pre-order traversal. Note that we are asked to do it in-place meaning we cannot allocate a new linked list to store the result. Furthermore, the binary tree is "right" flatten, meaning each parent points to its right child. 

Solution:
The basic idea is to use pre-order traversal. For a parent node, merge its left subtree to its right child, append the rest of the rest subtree to the right most child of the left substree. Then recursively move to its right child. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root){
        if (root == null) return;
        
        if (root.left != null) {
            TreeNode rChild = root.right;
            root.right = root.left;
            root.left = null;
            TreeNode rMost = root.right;
            while (rMost.right != null) {
                rMost = rMost.right;
            }
            rMost.right = rChild;
        }
        
        flatten(root.right);
    }
}

Iterative Solution:
Since preorder traversal can be done iteratively, can we solve this problem in an iterative way? The answer is yes. In similar to the preorder traversal, we can employ a stack to solve the problem. 

The basic idea is for a node, if it has right child, push it to the stack first. Then check its left child, if not null, connect it to the right end; else, pop a node from the stack and append it to the right end.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root){
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        
        TreeNode p = root;
        
        while (p != null || !stack.empty()) {
            if (p.right != null) {
                stack.push(p.right);
            }
            
            if (p.left != null) {
                p.right = p.left;
                p.left = null;
            } else if (!stack.empty()) {
                TreeNode temp = stack.pop();
                p.right = temp;
            }
            
            p = p.right;
        }
    }
}

A better solution:
Here is a better solution without using stacks. So the space complexity is O(1). And the code structure is almost the same as recursive solution.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root){
        if (root == null) return;
        TreeNode p = root;
        
        while (p.left != null || p.right != null) {
            if (p.left != null) {
                TreeNode rChild = p.right;
                p.right = p.left;
                p.left = null;
                TreeNode rMost = p.right;
                while (rMost.right != null) {
                    rMost = rMost.right;
                }
                rMost.right = rChild;
            }
            
            p = p.right;
        }
    }
}

Summary:
In this post, we learned how to flatten a tree to a linked list. Note the idea of pre-order traversal, and its variants. Also be careful that when you move a node in a tree, all its subtrees will be moved as well, similar to linked list. 

Update on 4/15/15:
An iterative solution which is just transformed from the recursive one. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }        
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            
            if (curr.right != null) {
                stack.push(curr.right);
            }
            
            if (curr.left != null) {
                stack.push(curr.left);
            }
            
            if (curr.left != null) {
                TreeNode rChild = curr.right;
                curr.right = curr.left;
                curr.left = null;
                
                // find the right most child
                TreeNode rightMostChild = curr.right;
                while (rightMostChild.right != null) {
                    rightMostChild = rightMostChild.right;
                }
                rightMostChild.right = rChild;
            }
        }
    }
}

However, we could see from this solution that it is not very inefficient; it will repeatedly add nodes into the stack and pop them out. 

Leetcode: LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Understand the problem:
The problem asks for implementing a LRU cache. It should support the following operations get and set. 

The crux of the problem is of deep understanding the LRU cache. The LRU cache is least recently used. That is, when insert a new item, it will kick out the least recently used item into the next lower level memory. Suppose the top of the LRU means mostly recently used, and the tail is least recently used. When we get a value from a specific key, the item should be moved to the head as well, since it is mostly recently used. When update an item, the updated item should go to head. When insert a new item, the new item should be inserted to the head of the cache. When the cache capacity reaches, we shall first delete the tail node first before we insert a new node at head. 

Solution:
Note that all cache operations require O(1) time complexity. To achieve, we use hash map + doubly linked list. Why we use doubly linked list? Because we when delete a node or move the node to head, we shall do it in O(1) time. A singly linked list cannot achieve this. 

Code (Java): 

public class LRUCache {
    private int capacity;
    private HashMap<Integer, Node> map = new HashMap<Integer, Node>();
    private Node head;
    private Node tail;
    private int len;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        len = 0;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            Node temp = map.get(key);
            removeNode(temp);
            insertHead(temp);
            
            return temp.val;
        } else {
            return -1;
        }
    }
    
    public void set(int key, int value) {
        if (map.containsKey(key)) {
            Node temp = map.get(key);
            // update the node
            temp.val = value;
            
            removeNode(temp);
            insertHead(temp);
            map.put(key, temp);

        } else { // do not contain
            Node temp = new Node(key, value);
            if (len < capacity) {
                insertHead(temp);
                map.put(key, temp);
                len++;
            } else if (len == capacity) {
                map.remove(tail.key);
                removeTail();
                insertHead(temp);
                map.put(key, temp);
            }
        }
    }
    
    private void removeNode(Node node) {
        Node curNode = node;
        Node preNode = node.pre;
        Node nextNode = node.next;
        
        if (preNode == null) {
            head = head.next;
            if (head == null) tail = head;
            else head.pre = null;
        } else if (nextNode == null) {
            tail = tail.pre;
            if (tail == null) head = tail;
            else tail.next = null;
        } else {
            preNode.next = nextNode;
            nextNode.pre = preNode;
        }
    }
    
    private void insertHead(Node node) {
        if (head == null) {
            head = node;
            tail = head;
            head.pre = null;
            tail.next = null;
        } else {
            node.next = head;
            head.pre = node;
            head = node;
            head.pre = null;
        }
    }
    
    private void removeTail() {
        tail = tail.pre;
        if (tail == null) head = tail;
        else tail.next = null;
    }
    
    
    // Doubly linked list
    private class Node {
        public int key;
        public int val;
        public Node pre;
        public Node next;
        
        Node (int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}

Discussion:
Note in Line 58 and 62, handle the null pointer exception. That is, if the head or tail node is null, you cannot set its pre node and next node to null as well. 

In this solution, all operations take O(1) time. Since we used hash map to store the key-node pairs, the space complexity is O(n) in additional to the O(n) cost on storing the linked list. 
Summary:
This question is kind of complicated to implement. It is unlikely to implement the full LRU during a code interview. However, you can at least answer the hash map + doubly linked list solution.  Note the doubly linked list idea. If you are asked to insert or delete an item in O(1) time, doubly linked list is a good candidate. 

Leetcode: Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Understand the problem:
The problem asks for partition a linked list according to a given value x such that all nodes less than x come before nodes greater than or equal to x. 
Also note that the problem asks for the stable partitioning, i.e, preserve the original relative order of the nodes in each of the two partitions. 

We can take several examples to illustrate the problem. 
Given 1 -> 4 -> 3 -> 2 ->5 ->2, and x = 3,
return 1 -> 2 -> 2 -> 3 -> 4 -> 5 (WRONG) See the analysis later

Given 1 -> 2 -> 6 -> 3 -> 2 -> 1, and x = 3
return 1- > 2 -> 2-> 1-> 3 -> 6 (WRONG) See the analysis later

Naive Solution:
Since the problem does not require a in-place partition, one native solution is to scan the linked list once and picked up the nodes less than the pivot. Then append the pivot to the end of the linked list. Finally, scan the list again and append the nodes greater or equal to x.
For this solution, the time complexity is O(n) + O(n) = O(n). The space complexity is O(n) since it is out-of-place partition. 

A better solution:
In the naive solution, we scan the linked list twice and takes additional O(n) space. Can we just scan the list once and take less space? The answer is yes. We scan the list, when the node is less than x, move on and check next. If greater, construct a linked list only storing the greater nodes. If equal, we only need to count the number of nodes that are equal to the target. After we scan the linked list. We only need to append the equal nodes and greater nodes. 

Wrong Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        
        // create a helper node to avoid the complexities in updating the head node
        ListNode helper = new ListNode(Integer.MIN_VALUE);
        helper.next = head;
        head = helper;
        
        ListNode p = head;
        
        ListNode head2 = new ListNode(0);
        ListNode p2 = head2;
        int count = 0;
        
        while (p.next != null) {
            if (p.next.val < x) p = p.next;
            else if (p.next.val > x) {
                ListNode temp = p.next;
                p2.next = temp;
                p2 = p2.next;
                p.next = temp.next;
            } else {
                ListNode temp = p.next;
                p.next = temp.next;
                count++;
            }
        }
        p2.next = null;
        
        // append the equal nodes
        for (int i = 0; i < count; i++) {
            ListNode temp = new ListNode(x);
            p.next = temp;
            p = p.next;
        }
        
        // append the greater nodes
        p.next = head2.next;
        
        return head.next;
    }
}

Discussion:
The OJ returned the wrong answer:

Input:	{2,1}, 1
Output:	{1,2}
Expected:	{2,1}

But why? That is because we did not understand the problem correctly. The problem asks for partitioning the list such that all node less than x come before nodes greater OR EQUAL than x. For the example at beginning of the post, 

Given 1 -> 4 -> 3 -> 2 ->5 ->2, and x = 3,
return 1 -> 2 -> 2 -> 3 -> 4 -> 5 (WRONG) 
return 1 -> 2 -> 2 -> 4 -> 3 -> 5 (CORRECT)

Given 1 -> 2 -> 6 -> 3 -> 2 -> 1, and x = 3
return 1- > 2 -> 2-> 1-> 3 -> 6 (WRONG)
return 1 ->2 ->2 -> 1 -> 6 -> 3 (CORRECT)

In the code implementation, we don't need to handle the case where nodes are equal to x, and append the nodes before the nodes greater than x. Then the correct Java code is:

Correct Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        
        // create a helper node to avoid the complexities in updating the head node
        ListNode helper = new ListNode(Integer.MIN_VALUE);
        helper.next = head;
        head = helper;
        
        ListNode p = head;
        
        ListNode head2 = new ListNode(0);
        ListNode p2 = head2;
        int count = 0;
        
        while (p.next != null) {
            if (p.next.val < x) p = p.next;
            else {
                ListNode temp = p.next;
                p2.next = temp;
                p2 = p2.next;
                p.next = temp.next;
            }
        }
        p2.next = null;
        
        // append the greater or equal nodes
        p.next = head2.next;
        
        return head.next;
    }
}

Discussion:
Note that in the Line 36 above we must terminate the second list. That is because if not, it may cause a cyclic list. Take an example {3, 1} and x = 2. You will find the cycle. So make sure you understand exactly why we need to terminate the second list. 

This solution has time complexity of O(n) since we only iterate the list once. The space complexity is O(1) as we don't allocate new list to store the second linked list. Note that if we store the second list into another new linked list, there will be no cycle in the linked list and we don't need to handle this problem. But the space complexity becomes O(n) in the worst case. 

Summary:
This problem looks very like the first step of the quick sort. But quick sort is not a stable sorting algorithm. This problem, however, requires a stable partitioning algorithm. Make sure you understand well both the wrong solution and correct solution, as well as the cyclic linked list problem. 

Leetcode: Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Understand the problem:
The problem asks for removing duplicated numbers from a linked list. Note the the difference from the last post is all duplicated numbers are deleted.  For example,
1  ->  1  -> 1  -> 2  , return 2

For an empty linked list, return null
For a linked list with only 1 element, return the original linked list. 

Solution:
We still use two pointers, p and q. q pointer is one step ahead of p at beginning. Move q pointer if q is duplicated. If q pointer moves more than one steps (has duplicates), move p.next = q.next. Else, move p and q one step ahead. The crux is to determine if q moves multiple steps. If yes, it means q pointer has duplicates, we should jump the q pointer. Else, q pointer should be saved. For example,
0 -> 1  -> 2 ->3, where p and q points to 0 and 1, respectively. Since 1 has no duplicates afterwards, we move both p and q one step ahead.
0  -> 1  -> 1 -> 2  -> 3, where again p and q points to 0 and 1, respectively. Since now i has duplicates afterwards, we should jump the 1s and points p to the value of 2.

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode helper = new ListNode(0);
        helper.next = head;
        head = helper;
        
        ListNode p = head;
        ListNode q = head.next;
        
        while (q != null) {
            while (q.next != null && q.val == q.next.val) {
                q = q.next;
            }
            if (p.next != q) {
                p.next = q.next;
                if (q != null) q = q.next;
            } else {
                p = p.next;
                q = q.next;
            }
        }
        return head.next;
    }
}

Discussion:
Note that we used a helper node ahead of the head node. This is to avoid the complexities in deleting the head node, which may be the case for this question.  Using helper node is a common usage when updating the head node.

Updates on 10/7/14:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(Integer.MIN_VALUE);
        dummyNode.next = head;
        
        ListNode prev = dummyNode;
        ListNode curr = head;
        
        while (curr != null && curr.next != null) {
            ListNode next = curr.next;
            if (curr.val == next.val) {
                while (curr.next != null && curr.val == next.val) {
                    curr = curr.next;
                    next = next.next;
                }
            
                prev.next = next;
                curr = next;
            } else {
                prev = prev.next;
                curr = curr.next;
            }
        }
        
        return dummyNode.next;
    }
}

Leetcode: Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Understand the problem:

The question asks for removing duplicates in a linked list.

For example, 1  -> 1  -> 2, return 1  -> 2

For the linked list is null or empty, return the empty linked list

For the linked list having only one element, return the original linked list

Note that the question does not require in-place transform. The out-of-place solution is clearly simple: we just create a new linked list without duplicated elements. But can we do it in-place?

Solution:

Use two pointers, p and q, q is ahead of p at beginning. Compare the value of p and q, if different, move both p and q, else move the q pointer until they are different again. 

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        
        ListNode p = head;
        ListNode q = head.next;
        
        while (q != null) {
            if (p.val != q.val) {
                p = p.next;
                q = q.next;
            } else {
                p.next = q.next;
                q = q.next;
            }
        }
        return head;
    }
}

Summary:
The problem is very straight-forward, but be very careful to handle the null-pointer well when moving the pointer.