LinkedList

206. Reverse Linked List

Java

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curt = head;
        while (curt != null) {
            ListNode next = curt.next;
            curt.next = prev;
            prev = curt;
            curt = next;
        }
        return prev;
    }

Python

    def reverseList(self, head: ListNode) -> ListNode:
        pre = None 
        curt = head
        while curt != None:
            nxt = curt.next
            curt.next = pre
            pre = curt
            curt = nxt
        return pre

Recursion

    ListNode newhead = null;
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        helper(head);
        return newhead;
    }
    
    private ListNode helper(ListNode curt) {
        if (curt.next == null) {
            newhead = curt;
            return curt;
        }
        ListNode next = helper(curt.next);
        curt.next.next = curt;
        curt.next = null;
        return next;
    }

83. Remove Duplicates from Sorted List

Use a curt pointer and a nxt pointer to move from head. Detect if curt.val == nxt.val then remove nxt node.

    def deleteDuplicates(self, head: ListNode) -> ListNode:
        curt = head
        while curt is not None:
            nxt = curt.next
            if nxt and nxt.val == curt.val:
                curt.next = nxt.next
            else:
                curt = curt.next
        return head

21. Merge Two Sorted Lists

Use dummy node, and a current node starts at dummy. While the first and second list is not null, add the smaller node and move forward.

When end, detect the unfinished list, add to the end.

Iteration T: O(n + m) S: O(1)

Java

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curt = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curt.next = l1;
                l1 = l1.next;
            } else {
                curt.next = l2;
                l2 = l2.next;
            }
            curt = curt.next;
        }
        if (l1 == null) {
            curt.next = l2;
        }
        if (l2 == null) {
            curt.next = l1;
        }
        return dummy.next;
    }

Python

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(-1)
        curt = dummy
        while l1 and l2:
            if l1.val < l2.val:
                curt.next = l1
                l1 = l1.next
            else:
                curt.next = l2
                l2 = l2.next
            curt = curt.next
        if l1:
            curt.next = l1
        if l2:
            curt.next = l2
        return dummy.next

Recursion T: O(n + m) S: O(m + n)

Python

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 == None and l2 == None:
            return None
        if l1 != None and l2 == None:
            return l1
        if l1 == None and l2 != None:
            return l2
        if l1.val <= l2.val :
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else :
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

Java

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        else if (l1 == null) return l2;
        else if (l2 == null) return l1;
        else {
            if (l1.val < l2.val) {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            } else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }

23. Merge k Sorted Lists

1. Divide and Conquer, Merge sort T: O(n*logk) S: O(1)

Java

    public ListNode mergeKLists(ListNode[] lists) {
        return helper(lists, 0, lists.length - 1);
    }
    
    private ListNode helper(ListNode[] lists, int start, int end) {
        if (start == end) return lists[start];
        else if (start > end) {
            return null;
        } else {
            int mid = start + (end - start) / 2;
            return mergeTwo(helper(lists, start, mid), helper(lists, mid + 1, end));
        }
    }
    
    private ListNode mergeTwo(ListNode A, ListNode B) {
        if (A == null) return B;
        if (B == null) return A;
        if (A.val < B.val) {
            A.next = mergeTwo(A.next, B);
            return A;
        } else {
            B.next = mergeTwo(A, B.next);
            return B;
        }
    }

Python

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        return self.merge(0, len(lists) - 1, lists)
    
    def merge(self, left, right, lists) :
        if left > right:
            return None
        if left == right :
            return lists[left]
        mid = (left + right) // 2
        return self.mergeTwoLists(self.merge(left, mid, lists), self.merge(mid + 1, right, lists))
    
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(-1)
        curt = dummy
        while l1 and l2:
            if l1.val < l2.val:
                curt.next = l1
                l1 = l1.next
            else:
                curt.next = l2
                l2 = l2.next
            curt = curt.next
        if l1:
            curt.next = l1
        if l2:
            curt.next = l2
        return dummy.next

2. PQ T: O(nlogk) S: O(n)

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((l1, l2) -> Integer.compare(l1.val, l2.val));
        for (ListNode list : lists) {
            if (list == null) {
                continue;
            }
            pq.offer(list);
        }   
        ListNode dummy = new ListNode(-1);
        ListNode iterator = dummy;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            iterator.next = node;
            iterator = node;
            if (node.next != null) {
                pq.offer(node.next);
            } 
        }
        return dummy.next;
    }

2. Add Two Numbers

Construct node and take carry.

T: O(max(m, n)) S: O(max(m, n))

Java

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        int carry = 0;
        ListNode node = dummy;
        while (l1 != null || l2 != null || carry != 0) {
            int v1 = l1 == null ? 0 : l1.val;
            int v2 = l2 == null ? 0 : l2.val;
            int sum = v1 + v2 + carry;
            carry = sum / 10;
            node.next = new ListNode(sum % 10);
            node = node.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }

Python

class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode(-1)
        temp = dummy
        t1 = l1
        t2 = l2
        carry = 0
        while t1 or t2:
            if t1:
                val1 = t1.val
            else:
                val1 = 0
            if t2:
                val2 = t2.val
            else:
                val2 = 0
            sum_v = carry + val1 + val2
            carry = sum_v // 10
            sum_v = sum_v % 10
            new_node = ListNode(sum_v)
            temp.next = new_node
            temp = new_node
            if t1:
                t1 = t1.next
            if t2:
                t2 = t2.next
        if carry:
            new_node = ListNode(carry)
            temp.next = new_node
            temp = new_node
        return dummy.next

445. Add Two Numbers II

Use two stacks to store two lists separately. Pop node and construct new node, insert between dummy and dummy.next.

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        while (l1 != null) {
            s1.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            s2.add(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode dummy = new ListNode(0);
        while (!s1.isEmpty() || !s2.isEmpty()) {
            int one = s1.isEmpty() ? 0 : s1.pop();
            int two = s2.isEmpty() ? 0 : s2.pop();
            int sum = one + two + carry;
            ListNode curt = new ListNode(sum % 10);
            carry = sum / 10;
            curt.next = dummy.next;
            dummy.next = curt;
        }
        if (carry == 1) dummy.val = 1;
        return dummy.val == 1 ? dummy : dummy.next;
    }

141. Linked List Cycle

    def hasCycle(self, head: ListNode) -> bool:
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

142. Linked List Cycle II

   def detectCycle(self, head: ListNode) -> ListNode:
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                fast = head
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                return fast
        return None

24. Swap Nodes in Pairs

    def swapPairs(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        pre = dummy
        curt = head
        while curt is not None and curt.next is not None:
            nxt = curt.next
            curt.next = nxt.next
            nxt.next = pre.next
            pre.next = nxt
            pre = curt
            curt = pre.next
        return dummy.next

328. Odd Even Linked List

    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        even = head
        odd = head.next
        oddhead = odd
        while odd and odd.next:
            even.next = odd.next
            even = even.next
            odd.next = even.next
            odd = odd.next
        even.next = oddhead
        return head
        

92. Reverse Linked List II

• 记录一个pre，把pre移动到开始reverse的前面

• pre不动，把后面的reverse，把next接在pre和pre.next 中间

• Return dummy.next

T: O(n) S: O(1) in-place

 public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i < m - 1; i++) {
            pre = pre.next;
        }
        ListNode curt = pre.next;
        for (int i = 0; i < n - m; i++) {
            ListNode next = curt.next;
            curt.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }

19. Remove Nth Node From End of List

• 一个fast, 一个slow 都从dummy 走

• Fast走 i = 0 ： n。这样fast和尾的距离是total - n，

• slow，fast同时走，fast是null的时候，slow走了total -n ，slow和尾的距离是n

• 删除slow后面节点

    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head
        fast = dummy
        slow = dummy
        i = 0
        while i <= n and fast:
            fast = fast.next
            i += 1
        while fast:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

83. Remove Duplicates from Sorted List

一个指针，如果curt.val == curt.next.val 情况下curt.next = curt.next.next

    def deleteDuplicates(self, head: ListNode) -> ListNode:
        curt = head
        while curt is not None:
            nxt = curt.next
            if nxt and nxt.val == curt.val:
                curt.next = nxt.next
            else:
                curt = curt.next
        return head

82. Remove Duplicates from Sorted List II

• 两个指针走，在curt.next.val == curt.val情况下移动curt

• 如果pre的下一个不是curt，说明有duplicate，

• 否则同时移动pre和curt

    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head
        pre = dummy
        curt = head
        while curt is not None:
            while curt.next is not None and curt.val == curt.next.val :
                curt = curt.next
            if pre.next is not curt:
                pre.next = curt.next
                curt = pre.next
            else :
                pre = pre.next
                curt = pre.next
        return dummy.next

203. Remove Linked List Elements

Curt从dummy走，在curt.next.val == val的情况下，curt.next = curt.next.next

    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if head is None:
            return None
        dummy = ListNode(-1)
        dummy.next = head
        pre = dummy
        curt = head
        while curt is not None:
            if curt.val == val:
                curt = curt.next
                pre.next = curt
            else :
                pre = pre.next
                curt = curt.next
        return dummy.next

369. Plus One Linked List

这个题要说把linkedlist最后一个节点+1。如果有进位的话加到前面那个node。这样对于单向列表很麻烦，用recursion做非常直观。

• 如果碰到null，return 1，因为最后一位+1；

• 加上carry之后如果大于9，reassign value.返回1

• 否则返回0

• 这样的话有可能多出来一个node，用dummy来处理

160. Intersection of Two Linked Lists

先把两个list的长度求出来，减少长的那个，这样如果他们相等，就代表他们到最后的距离是相等的。这样说明两个head继续走，走到他们相等的时候就return。否则return null.

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = getLen(headA);
        int lenB = getLen(headB);
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }
        while (lenA < lenB) {
            headB = headB.next;
            lenB--;
        }
        
        while (headA != null || headB != null) {
            if (headA == headB) return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
    
    private int getLen(ListNode head) {
        int count = 0;
        while (head != null) {
            head = head.next;
            count++;
        }
        return count;
    }

Same method as 141, 142.

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode dummyA = headA;
        ListNode dummyB = headB;
        while (headA != headB) {
            headA = headA == null ? dummyB : headA.next;
            headB = headB == null ? dummyA : headB.next;
        }
        return headA;
    }

138. Copy List with Random Pointer

Use a Hash-map to store original and it is corresponding new node. Loop over it and set the random pointer.

    public Node copyRandomList(Node head) {
        Node dummy = new Node(-1);
        Node pre = dummy;
        Node curt = head;
        Map<Node, Node> map = new HashMap<>();
        while (curt != null) {
            map.putIfAbsent(curt, new Node(curt.val));
            pre.next = map.get(curt);
            curt = curt.next;
            pre = pre.next;
        }
        curt = head;
        while (curt != null) {
            map.get(curt).random = map.get(curt.random);
            curt = curt.next;
        }
        return dummy.next;
    }

Add the new node next to the original node. For example 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null

    public Node copyRandomList(Node head) {
        Node dummy = new Node(-1);
        Node curt = head;
        while (curt != null) {
            Node sec = curt.next;
            curt.next = new Node(curt.val);
            curt.next.next = sec;
            curt = sec;
        }
        curt = head;
        Node pre = dummy;
        while (curt != null) {
            if (curt.random != null) curt.next.random = curt.random.next;
            curt = curt.next.next;
        }
        curt = head;
        while (curt != null) {
            Node nxt = curt.next;
            curt.next = nxt.next;
            pre.next = nxt;
            pre = pre.next;
            curt = curt.next;
        }
        return dummy.next;
    }

234. Palindrome Linked List

Palindrome特性是从中间到两边对称。一般Palindrome都涉及到单双数的问题。这个题也是找中点，然后从中点往两边比较是不是Palindrome。

• 找中点用快慢指针, while (fast.next != null && fast.next.next != null)

• Fast到头之后，check一下fast是不是null，如果不是，说明是even，slow还要往前走一个。

• 这样从slow到尾reverse()。用reverse LinkedList变成这样：
• 最后从head和slow 走，看看是不是相等

    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True
        fast = head
        pre = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            pre = slow
            slow = slow.next
        if fast:
            pre = pre.next
        curt = pre.next
        while curt and curt.next:
            nxt = curt.next
            curt.next = nxt.next
            nxt.next = pre.next
            pre.next = nxt
        fast = head
        slow = pre.next
        while slow and fast:
            if fast.val != slow.val:
                return False
            fast = fast.next
            slow = slow.next
        return True

86. Partition List

    def partition(self, head: ListNode, x: int) -> ListNode:
        largehead = ListNode(-1)
        largecurt = largehead
        dummy = ListNode(-1)
        dummy.next = head
        pre = dummy
        curt = head
        while curt:
            if curt.val >= x:
                pre.next = curt.next
                curt.next = largecurt.next
                largecurt.next = curt
                largecurt = curt
                curt = pre.next
            else:
                pre = pre.next
                curt = curt.next
        pre.next = largehead.next
        return dummy.next

143. Reorder List

从 1->2->3->4, reorder it to 1->4->2->3。这样可以把list分成左右两段，反转后面的，然后相互插入形成结果。

• 快慢指针找中点，把slow记录一下成为preMiddle，然后slow = slow.next;

• 这样preMiddle后面的，也就是从slow开始，都要reverse。就是把slow.next都插入到preMiddle.next。

• 然后再互相merge

    def reorderList(self, head: ListNode) -> None:
        if not head or not head.next:
            return
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        curt = slow.next
        while curt and curt.next:
            nxt = curt.next
            curt.next = nxt.next
            nxt.next = slow.next
            slow.next = nxt
        fast = slow.next
        slow.next = None
        slow = head
        while fast and slow:
            fn = fast.next
            fast.next = slow.next
            slow.next = fast
            slow = fast.next
            fast = fn

148. Sort List

这题一看就是merge sort。跟传统merge sort一样，不过最后要merge两个list。还是先快慢指针分一半。用一个pre记录slow之前的点，然后把pre.next = null;这样recursively两边再分，最后merge。 Merge时候注意null pointer

61. Rotate List

这个题是说把后面数k个Node接到前面去，有个情况就是k会比总长度大。k % length == 0 说明不用rotate。这种情况用k % length就会得到从前往后要多少个接到前面， length - k % length是从后往前有多少接到前面。

先一个指针找长度，另外一个指针走length - k % length，把两个指针中间接到前面去。（两个指针都从dummy 走）

    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next or k == 0:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        length = self.getLen(head)
        pre = dummy
        if k % length == 0:
            return dummy.next
        for i in range(length - k % length):
            pre = pre.next
        curt = pre.next
        pre.next = None
        dummy.next = curt
        while curt and curt.next:
            curt = curt.next
        if curt:
            curt.next = head
        return dummy.next
    
    def getLen(self, head):
        i = 0
        curt = head
        while curt:
            i += 1
            curt = curt.next
        return i

25. Reverse Nodes in k-Group

Use a range pointer to detect if the range is out of scope. Reverse the part next to pre for k - 1 times.

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode range = pre;
        while (true) {
            for (int i = 0; i < k && range != null; i++) {
                range = range.next;
                if (range == null) return dummy.next;
            }
            ListNode curt = pre.next;
            for (int i = 0; i < k - 1; i++) {
                ListNode next = curt.next;
                curt.next = next.next;
                next.next = pre.next;
                pre.next = next;
            }
            pre = curt;
            range = pre;
        }
    }