Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        
        Queue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), ListCom);
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                queue.offer(lists.get(i));   
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (!queue.isEmpty()) {
            ListNode cur = queue.poll();
            head.next = cur;
            if (cur.next != null) {
                queue.offer(cur.next);
            }
            head = head.next;
        }
        return dummy.next;
    }
    
    private Comparator<ListNode> ListCom = new Comparator<ListNode>() {
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }  
    };
}

Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

只要最后检查下进位是不是1。

public class Solution {
    //Time: O(n)
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        
        int carry = 0;
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                carry += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                carry += l2.val;
                l2 = l2.next;
            }
            node.next = new ListNode(carry % 10);
            carry /= 10;
            node = node.next;
        }
        if (carry == 1) {
            node.next = new ListNode(1);
        }
        return dummy.next;
    }
}

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

计算一共要反转多少个group，对每个gruop在反转k-1次。

public class Solution {
    //Time: O(n)  Space: O(1)
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        
        int length = getLength(head);
        int num = length / k;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        int i = 0;
        while (i < num) {
            int j = 0;
            while (j < k - 1) {
                ListNode tmp = head.next;
                head.next = tmp.next;
                tmp.next = pre.next;
                pre.next = tmp;
                j++;
            }
            pre = head;
            head = pre.next;
            i++;
        }
        return dummy.next;
    }
    
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
}

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.

当发现相邻node值一样，记录这个值，把下面和这个值相等的Node都删除。注意Null check。

public class Solution {
    //Time: O(n)  Space: O(1)
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while (head.next != null) {
            if (head.next.next != null && head.next.val == head.next.next.val) {
                int val = head.next.val;
                while (head.next != null && head.next.val == val) {
                    head.next = head.next.next;
                }
            } else {
                head = head.next;
            }
        }
        return dummy.next;
    }
}

Insertion Sort List

Sort a linked list using insertion sort.

public class Solution {

    //Time: O(n^2)
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        while (head != null) {
            ListNode node = dummy;
            while (node.next != null && node.next.val < head.val) {
                node = node.next;
            }
            
            ListNode temp = head.next;
            head.next = node.next;
            node.next = head;
            head = temp;
        }
        return dummy.next;
    }
}

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.

链表部分反转，找到开始反转的位置，反转 n - m次。

public class Solution {
    //Time: O(n)
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        
        for (int i = 0; i < m - 1; i++) {
            head = head.next;
        }
        int num = 0;
        ListNode pre = head;
        head = head.next;
        while (num < n - m) {
            ListNode tmp = head.next;
            head.next = tmp.next;
            tmp.next = pre.next;
            pre.next = tmp;
            num++;
        }
        return dummy.next;
    }
}

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.

遍历原链表，用左右子链表，分别对应大于x小于x，最后把两部分连接起来。

public class Solution {
    //Time: O(n)  Space: O(1)
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummyleft = new ListNode(0);
        ListNode dummyright = new ListNode(0);
        ListNode left = dummyleft;
        ListNode right = dummyright;
        
        while (head != null) {
            if (head.val < x) {
                left.next = head;
                left = left.next;
            } else {
                right.next = head;
                right = right.next;
            }
            head = head.next;
        }
        
        left.next = dummyright.next;
        right.next = null;
        return dummyleft.next;
    }
}

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

每次二分法找中点，此点为root，左半部分为左子树，右半部分为右子树。

public class Solution {
    //Time: O(nlogn)
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        
        if (head.next == null || head.next.next == null) {
            TreeNode root = new TreeNode(head.val);
            if (head.next != null) {
                root.right = new TreeNode(head.next.val);
            }
            return root;
        }
        
        ListNode midPre = findMidPre(head);
        ListNode mid = midPre.next;
        TreeNode root = new TreeNode(mid.val);
        midPre.next = null;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);
        return root;
    }
    
    private ListNode findMidPre(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

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

把Tree变成LinkedList，我们需要一个额外的变量记录上一次变化到那个点，这样对于当前点，我们才能将它连接到上一个点。

public class Solution {
    //Time: O(n)
    private TreeNode last = null;
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        
        if (last != null) {
            last.left = null;
            last.right = root;
        }
        
        last = root;
        TreeNode right = root.right;
        flatten(root.left);
        flatten(right);
    }
}

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.

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //Time: O(n)  Space: O(1)
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

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.

public class Solution {
    //Time: O(n)  Space: O(1)
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while (head.next != null && head.next.next != null) {
            ListNode temp = head.next.next;
            head.next.next = temp.next;
            temp.next = head.next;
            head.next = temp;
            head = head.next.next;
        }
        return dummy.next;
    }
}

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

使用一个dummy node，对于要改变head node的链表，使用dummy node很有用。

public class Solution {
    //Time: O(n)  Space: O(1)
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                head.next = l2;
                l2 = l2.next;
            } else if (l2 == null) {
                head.next = l1;
                l1 = l1.next;
            } else {
                if (l1.val > l2.val) {
                    head.next = l2;
                    l2 = l2.next;
                } else {
                    head.next = l1;
                    l1 = l1.next;
                }
            }
            head = head.next;
        }
        return dummy.next;
    }
}

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.

public class Solution {
    //Time: O(n)  Space: O(1)
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode node = head;
        while (node.next != null) {
            if (node.next.val == node.val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
        return head;
    }
}

Linked List Cycle I & II

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

使用快慢指针，快指针走两部，慢指针走一步，如果两者相同则有环。

public class Solution {
    //Time: O(n)  Space: O(1)
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?
当判断有环后，让head和slow每次都一步，相遇即为环起点。

public class Solution {
    //Time: O(n)  Space: O(1)
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                break;
            }
        }
        if (fast.next == null || fast.next.next == null) {
            return null;
        }
        while (head != slow) {
            slow = slow.next;
            head = head.next;
        }
        return slow;
    }
}

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.

复制一个有random pointer的Linked List, 边遍历边构建List Node, 但是这里我们需要用到hashmap，这样保证了对于原来list里的每个node，我们只生成了一个与他对应的新node。
注意null check

public class Solution {
    //Time: O(n)
    public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode node = dummy;
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        while (head != null) {
            if (!map.containsKey(head)) {
                map.put(head, new RandomListNode(head.label));
            }
            node.next = map.get(head);
            //null check
            if (head.random != null) {
                if (!map.containsKey(head.random)) {
                    map.put(head.random, new RandomListNode(head.random.label));   
                }
                node.next.random = map.get(head.random);
            }
            head = head.next;
            node = node.next;
        }
        return dummy.next;
    }
}