ZXAlgorithm - C6 LinkedList and

Outline
LinkedList:
Dummy Node
High Frequency
Array:
Sorted Array
Subarray

0 Template

• Dummy Node
  When the structure changes, use dummy node
  Dummy, pre, curt
  Need dummy.next
  Dummy = new; dummy.next = head; head = dummy; return dummy.next; give the start of the linked list
• Worth to do questions

1 LinkedList

• Dummy Node
  Leetcode 25.Reverse Nodes in K-groups
  https://leetcode.com/problems/reverse-nodes-in-k-group/description/
  https://www.jiuzhang.com/solutions/reverse-nodes-in-k-group/
  S: I, dummy, begin
  D: reverse(begin, end)
  {S: begin end/first, prev, curt, next
  D: moving each times
  E: curt != end, return first}
  E: dummy.next
  链表结构发生变化时就需要Dummy Node
  如何使用 Dummy Node
  head = dummy 这句话总是需要么？
  什么时候使用 Dummy Node?
  Dummy Node 是否需要删除？
  使用 Dummy Node 算面试官会说我耗费了额外空间么？
  Dummy Node 非用不可么？
  Dummy Node 初始化的值重要么？
  链表的问题都需要用到 Dummy Node 么？

• Related Questions
  Leetcode 86.partition list
  https://leetcode.com/problemset/all/?search=partition%20list
  https://www.jiuzhang.com/solutions/?search=partition%20list
  Leetcode 21.Merge Two Sorted Lists
  https://leetcode.com/problemset/all/?search=merge%20two%20sorted%20lists
  https://www.jiuzhang.com/solutions/?search=merge%20two%20sorted%20lists
  Leetcode 206.Reverse Linked List
  2(cur)->1
  3(head)->4(head.next)->5
  https://leetcode.com/problemset/all/?search=reverse%20linked%20list
  https://www.jiuzhang.com/solutions/?search=reverse%20linked%20list
  Leetcode 206.Reverse Linked List II
  https://leetcode.com/problems/reverse-linked-list-ii/
  https://www.jiuzhang.com/solutions/?search=reverse%20linked%20list
  Leetcode 143.Reorder List
  快慢指针，分成两段，重新连接
  https://leetcode.com/problemset/all/?search=reorder%20list
  https://www.jiuzhang.com/solutions/?search=reorder%20list
  Leetcode 61.Rotate List
  分成两段，重新拼接
  https://leetcode.com/problemset/all/?search=rotate%20list
  https://leetcode.com/problems/rotate-list/discuss/22842/97.63-Python-Solution
  https://www.jiuzhang.com/solutions/?search=rotate%20list

• Copy
  Leetcode 138.Copy List with Random Pointer
  https://leetcode.com/problemset/all/?search=Copy%20List%20with%20Random%20Pointer
  https://www.jiuzhang.com/solutions/?search=Copy%20List%20with%20Random%20Pointer
  Version 1
  S: g: map, head, dummy, pre, newNode;
  D: while(head check; head.random check)
  E: dummy.next;
  Version 2
  S:
  D: Use hashmap
  No extra space
  Copy random: Head.next.random = head.random.next

• LinkedList cycle
  Linked List Cycle 1& 2
  https://leetcode.com/problemset/all/?search=Linked%20List%20Cycle
  https://www.jiuzhang.com/solutions/?search=Linked%20List%20Cycle
  http://www.lintcode.com/en/problem/linked-list-cycle/ http://www.jiuzhang.com/solutions/linked-list-cycle/
  follow up: http://www.lintcode.com/en/problem/linked-list-cycle-ii/ http://www.jiuzhang.com/solutions/intersection-of-two-linked-lists/

  • Cycle check if it has
    S: fast = head.next , slow = head, head
    D: Runner technique
    Check fast and fast.next == null then return false
    Slow = slow.next
    Fast = fast.next.next
  • Cycle return the node where the cycle begin
    S: fast, slow, head
    D:Runner technique 2
    Runner technique 1
    head != slow.next then head = head.next slow = slow.next
    E: head

• Quick and merge sort list
  Sort List
  https://leetcode.com/problemset/all/?search=Sort%20List
  https://www.jiuzhang.com/solutions/?search=Sort%20List
  http://www.lintcode.com/en/problem/sort-list/ http://www.jiuzhang.com/solutions/sort-list/
  Merges: findMiddle, merge, sort
  Quicks: findMiddle, concat, gettail, sort

• Related question
  Convert Sorted List to Binary Search Tree
  https://leetcode.com/problemset/all/?search=Convert%20Sorted%20List%20to%20Binary%20Search%20Tree
  https://www.jiuzhang.com/solutions/?search=Convert%20Sorted%20List%20to%20Binary%20Search%20Tree
  Delete Node in a Linked List
  https://leetcode.com/problemset/all/?search=Delete%20Node%20in%20a%20Linked%20List
  https://www.jiuzhang.com/solutions/?search=Delete%20Node%20in%20a%20Linked%20List
  Convert Binary Search Tree to Doubly Linked List
  https://www.jiuzhang.com/solutions/?search=Convert%20Binary%20Search%20Tree%20to%20Doubly%20Linked%20List
  Other:
  http://www.lintcode.com/problem/convert-sorted-list-to-balanced-bst/
  http://www.lintcode.com/problem/delete-node-in-the-middle-of-singly-linked-list/
  http://www.lintcode.com/problem/convert-binary-search-tree-to-doubly-linked-list/

3 Array

• Sorted Array
  Merge Two Sorted Arrays
  https://leetcode.com/problemset/all/?search=Merge%20Two%20Sorted%20Arrays
  https://www.jiuzhang.com/solutions/?search=Merge%20Two%20Sorted%20Arrays
  D: small first, then big
  Merge Sorted Array
  https://leetcode.com/problemset/all/?search=Merge%20Sorted%20Array
  https://www.jiuzhang.com/solutions/?search=Merge%20Sorted%20Array
  D: same as above
  Median of Two Sorted Arrays
  http://www.lintcode.com/problem/median-of-two-sorted-arrays/ http://www.jiuzhang.com/solutions/median-of-two-sorted-arrays/

• Related questions
  Merge sorted array
  将小数组归并到大数组
  http://www.lintcode.com/problem/merge-sorted-array/
  http://www.jiuzhang.com/solutions/merge-sorted-array/
  Intersection of Two Arrays
  两个数组的交
  https://leetcode.com/problemset/all/?search=Intersection%20of%20Two%20Arrays
  https://www.jiuzhang.com/solutions/?search=Intersection%20of%20Two%20Arrays
  Use two hashset
  Sort and compare
  Sort one and Binary search it

• Subarray
  令 PrefixSum[i] = A[0] + A[1] + … A[i - 1], PrefixSum[0] = 0 易知构造 PrefixSum 耗费 O(n) 时间和 O(n) 空间 如需计算子数组从下标i到下标j之间的所有数之和 则有 Sum(i~j) = PrefixSum[j + 1] - PrefixSum[i]
  Maximum Subarray
  https://leetcode.com/problemset/all/?search=Maximum%20Subarray
  https://www.jiuzhang.com/solutions/?search=Maximum%20Subarray
  S: max, sum, minSum
  D: Prefix sum: sum, max, minsum compare max and sum - minSum continued to update the lowest first values
  Sum += A[i]
  Max(sum, sum - minSum)
  Min(minSum, sum);
  Subarray sum
  http://www.lintcode.com/en/problem/subarray-sum/ http://www.jiuzhang.com/solutions/subarray-sum/
  S: List<Integer> ans, HashMap<Integer, Integer> map
  D: use sum to store the first n items, store it into map, compare which one is equal, use index difference to get result;
  Subarray Sum Closest
  http://www.lintcode.com/en/problem/subarray-sum-closest/ http://www.jiuzhang.com/solutions/subarray-sum-closest/