5. Linked List - swchen1234/Algorithm GitHub Wiki

理论

题型分类：

    1. 链表结构变化题
    • 1.1 Reverse
    • 1.2 Merge
    • 1.3 首尾相接
    • 1.4 拆分
    • 1.5 删除和添加
    1. 检测遍历
    • 2.1 检测环
    • 2.2 找中点
    • 2.3 计算
    1. 实现其它数据结构
    • 3.1 Design
    • 3.2 用 Mono Stack实现
    • 3.3 与Tree 相关
  • 4.其它/简单实现

TIPS:

  • 双指针： 快慢指针 vs 双向指针
  • Dummy Node, 不必担心多余空间， 可以使code clean 很多。Nearly 90% of the linked list question is solved with this trick.
  • C++ Dummy 小技巧: 不需要用new, 用ListNode dummy; dummy.next = head
  • 多注释， 多画图

链表的实现原理

node1 = ListNode(1)
node2 = ListNode(2), node1.next = node2
node3 = ListNode(3), node2.next = node3
head = node1 # head, node1中，只存放listnode的地址
print(head) # 1->2->3->null
node1 = node2 # 修改后node1指向node2, 不改变head
print(head) # 仍旧为1->2->3->null

比较ListNode

ListNode.__lt__ = lambda x, y: x and y and x.val < y.val

Problems

1. 链表结构变化题

1.1 Reverse

  • 两种方法 方法1:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

方法2:

def reverseListII(prev):
    tail = prev.next
    for _ in range(k):
       curr = tail.next
       tail.next = curr.next
       curr.next = prev.next
       prev.next = curr
   return prev.next

固定prev.tail, 只移动curr， 每次在dummy.next添加新加入的点，结束时都是一个完整的linkedlist. 适合只需要reverse k 个node的情况。

24. Swap Nodes in Pairs类似206， 有prev, p1, p2, nxt四个指针，中间调整prev， p2, p1的next
25. Reverse Nodes in k-Group先数k个到curr， 如已经到终点，则跳出；-> 用reverse list的第二种方法只reverse prev之后的k个点，tail=Reverse(prev), prev = tail.
206. Reverse Linked List
92. Reverse Linked List II固定prev,curr，每次将当前值逆转\

1.2 Merge

21. Merge Two Sorted Lists 23. Merge k Sorted Listsheap中存放(n.val, n)
148. Sort Listmerge sort
143. Reorder List拆分+逆序+合并
1669. Merge In Between Linked Lists

1.3 首尾相接

61. Rotate List先计算长度，k=k%length。法一：先练成圈，再切断，法二：先切断，再连结尾，不需要dummy\

1.4 拆分

328. Odd Even Linked List初始将oddHead=head, evenHead=head.next, 最后将oddHead的尾连接到evenHead
2130. Maximum Twin Sum of a Linked List找到中点 -> reverse后半段 -> 从两端向中间并拢，比较max pair
86. Partition List拆为两个list， <x和>=x,再相连
138. Copy List with Random Pointer复制->复制random pointer(p.random.next = p.next.random) -> 拆开
725. Split Linked List in Partsdivmod后， d, m = divmod(l, k), for i in k: size = d+1 if i < m else d\

1.5 删除和添加

19. Remove Nth Node From End of List同找中点，可以通过让fast先走n + 1步使得slow停留在待删除点之前。
83. Remove Duplicates from Sorted List 82. Remove Duplicates from Sorted List II只用p一个变量，若p.next.val==p.next.next.val,则设置临时变量tbd=p.next，移动tbd直至tbd.val!=tbd.net.val
203. Remove Linked List Elements直接比较p.next.val==val， 省区变量prev
237. Delete Node in a Linked List题目中只给欲删除点；解法：将下个点复制给当前点，删除下一个点
1171. Remove Zero Sum Consecutive Nodes from Linked Listhash中存presum node，每次遇到相同presum, pop直到之前出现的presum的那个结点，删除当中节点. one pass，用orderedDict实现\

1.6 其它

147. Insertion Sort List排序；建立dummyHead(next=None)， 对list中每个点，找到以dummy为首的新链表中的插入位置
430. Flatten a Multilevel Doubly Linked List由recursion解
708. Insert into a Sorted Circular Linked List找到第一个值介于prev和prev.next之间，或者prev < prev.next并且(其值>prev.val或者<prev.next), 若prev.next==head还没找到，那么prev后插入新点
1721. Swapping Nodes in a Linked List可以让fast先走k步，得右边交换点，再同时移动fast和slow,直至fast到头，此时slow指向左交换点,交换左右亮点的值\

2. 检测遍历

2.1 检测环

141. Linked List Cyclefast和slow指针相交则代表有环\

slow, fast = head, 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快慢指针相交后->将快指针放回队首，和慢指针同样速度移动，首次相交时即为交界处。a+b+k*c=2(a+b) => a+b = k*c => a = k*c-b
160. Intersection of Two Linked Lists This is classics. Move the fast pointer to the start of slow pts, they are guaranteed to meet if there is intersection.\

2.2 找中点

2095. Delete the Middle Node of a Linked List可以通过让fast先走一步使得slow停留在middle之前。\

    slow, fast = dummy, dummy.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

876. Middle of the Linked List 234. Palindrome Linked List Fast pointer moves two step, slow pointer reverse when moving. When the fast pointer reaches the end, the slow pointer will be in the middle. And the comparison two direction. 也可以用recursion解，利用全局变量front, recursion直至最后后节点curr, 比较front和curr, front向后移一格，返回递归上一层，继续比较front和curr, 程序简单，但空间度为O(n)\

2.3 计算

2. Add Two Numbers 445. Add Two Numbers II因为此处链表为正序，且链表长度不一，总是令l1更长，先连l1多余部分，再将l1和l2相同部分相加，得新链表后，reverse，同时将多余10的部分carry到下一个节点。
369. Plus One Linked List找到最右边一个不是9的数，+1, 之后的数设为0;若最右边的数==dummyHead， 返回dummyHead,否则返回dummyHead.next
1290. Convert Binary Number in a Linked List to Integer

2.4 其它

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points一次遍历,记录prevVal， 每次call isCritical(node)判断\

3. 实现其它数据结构

3.1 Design

622. Design Circular Queue用singly linked list即可实现，效果同deque
146. LRU Cache
460. LFU Cachekey2Value={key: (value, freq)}, freq2Key={freq: DLL(key, value)}, 其中DLL可以用OrderedDict代替
432. All Oone Data Structure类似于LFU，但（1）不需要维持同样freq的key的先后顺序（2）需要支撑key的+/-变化，所以LFU中用minFreq单个变调不够（即LRU中只会增加,故minFreq+1即可），所以使用{key:cnt},{cnt:DLL}
705. Design HashSet对key取模，用array of linked list head（open hash)
706. Design HashMap和705的唯一区别在于需要存value，所以可以customize ListNode{key, value, next}
1670. Design Front Middle Back Queue可以doubly linked list， 十分冗长；也可以用deque实现\

3.2 用 Mono Stack实现

1019. Next Greater Node In Linked Liststack中存(val, i)，若node.val > stack[-1][0], res[i]=node, one-pass
2487. Remove Nodes From Linked Liststack中存储node，使node.next=新加入的点\

3.3 与Tree 相关

109. Convert Sorted List to Binary Search Tree找到中点->divide conquer左右两边
114. Flatten Binary Tree to Linked List利用morris traversal,不断的将现在节点的左孩子 设为现在节点的右孩子， 现在节点原来的右孩子连接到原来左子树的最右。
1367. Linked List in Binary Treedfs，设两个递归函数,findHead和matchPath
426. Convert Binary Search Tree to Sorted Doubly Linked ListinOrder traversal的Iterative解法\

4.其它/简单实现

382. Linked List Random Node水塘抽样，每次以1/i的概率替换O(i)，遍历,i为当前长度\