双指针
在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针。
所谓左右指针，就是两个指针相向而行或者相背而行；而所谓快慢指针，就是两个指针同向而行，一快一慢。
对于单链表来说，大部分技巧都属于快慢指针，比如链表环判断，倒数第 K 个链表节点等问题，它们都是通过一个 fast 快指针和一个 slow 慢指针配合完成任务。
- 19. Remove Nth Node From End of List
- 83. Remove Duplicates from Sorted List
- 86. Partition List
- 142. Linked List Cycle II
- 160. Intersection of Two Linked Lists
- 876. Middle of the Linked List
解析
2. Add Two Numbers
- 先反转链表
- 用一个 bit 来保存是否要进位（carry）的状态
- 如果两个链表一长一短，如 1, 2->2->2，可视为 1->0->0, 2->2->2，即用0来补齐
# time: O(n+m)
# space: O(1)
def addTwoNumbers(self, l1, l2):
"""
:type l1: Optional[ListNode]
:type l2: Optional[ListNode]
:rtype: Optional[ListNode]
"""
dummy = ListNode()
cur = dummy
carry = 0
while l1 or l2 or carry: # 用 or carry 来解决 7+8的情况
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
# new digit
val = v1 + v2 + carry
carry = val // 10
val = val % 10
cur.next = ListNode(val)
# update ptrs
cur = cur.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
ref
19. Remove Nth Node From End of List
# Iteration (two pass)
# time: O(n) # O(2n)
# space: O(1)
def removeNthFromEnd(self, head, n):
"""
:type head: Optional[ListNode]
:type n: int
:rtype: Optional[ListNode]
"""
total = 0
p = head
while p:
total += 1
p = p.next
toRemoveIndex = total - n
if toRemoveIndex == 0: # 这样做后，就不需要引入dummy了
return head.next
p = head
for _ in range(total - n - 1):
p = p.next
p.next = p.next.next
return head
# Iteration (one pass) - two pointers + dummy
# time: O(n) # O(n)
# space: O(1)
# - 保证 L 和 R 指针的间隔是 n，当 R 到尾端时， L 指向的元素就是要移除的元素的前一个（prevL）
# - 注意 edge case:
# 1. 1 -> 2 -> 3, n = 3, 得到 2 -> 3 -> 引入 dummy 来解决
# 2. 1, n = 1，得到 empty
ref
- https://neetcode.io/solutions/remove-nth-node-from-end-of-list
- https://www.youtube.com/watch?v=XVuQxVej6y8
21. Merge Two Sorted Lists
# dummy
# - time: O(n+m)
# - space: O(1)
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
tail = dummy # use dummy node to avoid the edge case of empty list1 or list2
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1:
tail.next = list1
else:
tail.next = list2
return dummy.next
ref
- https://neetcode.io/problems/merge-two-sorted-linked-lists
- https://www.youtube.com/watch?v=XIdigk956u0&ab_channel=NeetCode
todo 23. Merge k Sorted Lists
# solution 1 - brute force
# time: O(nk)
# space: O(k)
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode()
p = dummy
p_list = []
for l in lists:
if l:
p_list.append(l)
while True:
cur_min = float('inf')
cur_min_p = None
cur_min_idx = -1
for idx, cur_p in enumerate(p_list):
if cur_p and cur_p.val < cur_min:
cur_min = cur_p.val
cur_min_p = cur_p
cur_min_idx = idx
if cur_min_p:
temp = cur_min_p.next
p.next = cur_min_p
p = p.next
p_list[cur_min_idx] = temp
else:
break
return dummy.next
# solution 2
# time: O(nlogk)
# space: O(k)
def mergeTwoList(self, list1, list2):
dummy = ListNode()
tail = dummy
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1:
tail.next = list1
else:
tail.next = list2
return dummy.next
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists or len(lists) == 0:
return None
while len(lists) > 1: # until I got 1 链表
temp = []
for i in range(0, len(lists), 2): # Merge k 个链表变成 k/2个, k/4个 ... 1个
list1 = lists[i]
list2 = lists[i + 1] if i + 1 < len(lists) else None
temp.append(self.mergeTwoList(list1, list2))
lists = temp
return lists[0]
ref
todo - 83. Remove Duplicates from Sorted List
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null)
return null;
ListNode node = head;
while(node.next !=null){
if(node.val == node.next.val){
// delete one node
node.next = node.next.next;
}else{
node = node.next;
}
}
return head;
}
}
ref
- https://neetcode.io/solutions/remove-duplicates-from-sorted-list
- https://www.youtube.com/watch?v=p10f-VpO4nE&t=1s
todo - 86. Partition List
ref
138. Copy List with Random Pointer
# brute force
# hashmap (two pass)
# - time: O(n)
# - space: O(n)
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
oldToCopy = {None: None}
cur = head
while cur:
copy = Node(cur.val)
oldToCopy[cur] = copy
cur = cur.next
cur = head
while cur:
copy = oldToCopy[cur]
copy.next = oldToCopy[cur.next]
copy.random = oldToCopy[cur.random]
cur = cur.next
return oldToCopy[head]
# Hash Map (One Pass)
# - time: O(n)
# - space: O(n)
# todo
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
oldToCopy = collections.defaultdict(lambda: Node(0))
oldToCopy[None] = None
cur = head
while cur:
oldToCopy[cur].val = cur.val
oldToCopy[cur].next = oldToCopy[cur.next]
oldToCopy[cur].random = oldToCopy[cur.random]
cur = cur.next
return oldToCopy[head]
# Space Optimized - I
# - time: O(n)
# - space: O(1)
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if head is None:
return None
l1 = head
while l1 is not None:
l2 = Node(l1.val)
l2.next = l1.next
l1.next = l2
l1 = l2.next
newHead = head.next
l1 = head
while l1 is not None:
if l1.random is not None:
l1.next.random = l1.random.next
l1 = l1.next.next
l1 = head
while l1 is not None:
l2 = l1.next
l1.next = l2.next
if l2.next is not None:
l2.next = l2.next.next
l1 = l1.next
return newHead
ref
- https://www.youtube.com/watch?v=5Y2EiZST97Y
- https://neetcode.io/problems/copy-linked-list-with-random-pointer
141. Linked List Cycle
- 判断链表中是否有环，可以用快慢指针，如果有环，快慢指针一定会相遇
# hashmap for cache
# - time: O(n)
# - space: O(n)
def hasCycle(self, head: Optional[ListNode]) -> bool:
seen = set()
cur = head
while cur:
if cur in seen:
return True
seen.add(cur)
cur = cur.next
return False
# fast and slow pointers
# - time: O(n)
# - space: O(1)
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
ref
- https://www.youtube.com/watch?v=gBTe7lFR3vc
- https://neetcode.io/problems/linked-list-cycle-detection
todo - 142. Linked List Cycle II
143 Reorder List
- 步骤
- 找到链表的中间元素
- 旋转链表的后半段
- 合并两条链表
# 先旋转后半部分链表
# 如果包含偶数元素，则得到 1 -> 2, 4 -> 3
# 如果包含奇数元素，则得到 1 -> 2 -> 3, 5 -> 4
def reorderList(self, head):
"""
:type head: Optional[ListNode]
:rtype: None Do not return anything, modify head in-place instead.
"""
if not head or not head.next:
return head
# find the middle node
# fast = head.next 使得当包含偶数元素时, fast最终指向中间左边的元素
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# reverse the second half of the linked list
# slow.next points to the beginning of the second half linked list， e.g.,
# 1 -> 2 -> 3 -> 4, r -> 2
# 1 -> 2 -> 3 -> 4 -> 5, r -> 3
r = slow.next
l = None
slow.next = None # 需要这样以避免形成环
while r:
p = r.next
r.next = l
l = r
r = p
# merge two half
head1 = head
head2 = l
while head2: # 这里的条件是 head2 而不是 head1，因为左半部分链表的长度 >= 右半部分
temp1, temp2 = head1.next, head2.next
head1.next = head2
head2.next = temp1
head1, head2 = temp1, temp2
return head
ref
146. LRU Cache
- get时，
- 直接从 hashmap 中读，使得 time 为 O(1)。移除并插入到 most frequently used。
- 不存在时，直接返回 -1
- put 时
- 如果不存在，插入到 most frequently used
- 要检查 cap，如果超了，移除 LRU node
- 如果已经存在，移除并插入到 most frequently used
- 如果不存在，插入到 most frequently used
# hashmap + double linked list
# - time: O(1) for each put() and get()
# - space: O(n)
class Node(object):
def __init__(self, key, val):
# key 需要存储在node里，否则当 cap 满时，从 LRUCache.rear 读出 lru node 后，无法得知 key，因而无法从 hashmap 中把该 node 删除
self.key, self.val = key, val
self.left, self.right = None, Node
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.m = {}
# front=most recent used, rear=LRU
self.front, self.rear = Node(0, 0), Node(0, 0)
self.front.right, self.rear.left = self.rear, self.front
# insert node at left
def insert(self, node):
node.left = self.front
node.right = self.front.right
self.front.right.left = node
self.front.right = node
# remove node from linked list
def remove(self, node):
node.right.left = node.left
node.left.right = node.right
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key in self.m:
node = self.m[key]
# update linked list
self.remove(node)
self.insert(node)
return node.val
else:
return -1
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
if key in self.m:
node = self.m[key]
node.val = value
# update linked list
self.remove(node)
self.insert(node)
else:
if len(self.m) == self.capacity:
# remove the least frequently used node
node = self.rear.left
self.remove(node)
del self.m[node.key]
node = Node(key, value)
self.m[key] = node
self.insert(node)
ref
206. Reverse Linked List
# 没看懂
# recursive
# - time: O(n)
# - space: O(n)
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
newHead = head
if head.next:
newHead = self.reverseList(head.next)
head.next.next = head
head.next = None
return newHead
# iteration (two pointers)
# time: O(n)
# space: O(1)
def reverseList(self, head):
"""
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
"""
# 要把 prev 指向 None, 否则如果是 prev, curr = head, head.next，循环结束后 head 仍然会指向 head 之前指向的元素，从而形成了 circle
prev, curr = None, head
while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
return prev
ref
92. Reverse Linked List II
- edge case
- 1: left 可能为1，所以如果加上dummy，会更好处理
- left == right，这时不需要发生任何旋转
# dummy + 反转链表基础
# - time: O(n)
# - space: O(1)
def reverseBetween(self, head, left, right):
"""
:type head: Optional[ListNode]
:type left: int
:type right: int
:rtype: Optional[ListNode]
"""
if left == right:
return head
# 1) reach node at position "left"
dummy = ListNode(0, head)
leftPrev, cur = dummy, head
for _ in range(left - 1): # cur 指向 index 1元素，需要让 cur 指向 index left元素，因而移动 left -1次
leftPrev = leftPrev.next
cur = cur.next
# Now cur = "left", leftPrev = "node before left"
# 2) reverse from left to right
prev = None
for _ in range(right - left + 1): # 循环需要执行 right-left+1 次，即移动这么多次
temp = cur.next
cur.next = prev
prev = cur
cur = temp
# 3) update pointers
leftPrev.next.next = cur # cur is the node after "right"
leftPrev.next = prev # prev is "rightT"
return dummy.next
ref
160. Intersection of Two Linked Lists
# Hashset
# 先将一个链表中的所有值都分别存到HashSet中，再遍历另一个链表，当第一次找到存在于哈希表中的节点时，这个节点就是两链表的交叉点。
# 如果遍历到这个链表的尾部时，仍然没有找到有任何节点存在于哈希表中，则表明两链表没有交叉点（于是 return null）。
# - time: O(m+n)
# - space: O(m)
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
nodeSet = set()
cur = headA
while cur:
nodeSet.add(cur)
cur = cur.next
cur = headB
while cur:
if cur in nodeSet:
return cur
cur = cur.next
return None
# 双指针长度差值法 - 计算出两条链表的长度，求出长度差，在长的链表上的指针先跑"长度差"步，如两指针相遇，则存在交集。否则不存在
# - time: O(m+n)
# - space: O(1)
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
# Count the len
aLen, bLen = 0, 0
p = headA
while p:
aLen += 1
p = p.next
p = headB
while p:
bLen += 1
p = p.next
diff = abs(aLen - bLen)
pA = headA
pB = headB
if aLen > bLen:
for _ in range(diff):
pA = pA.next
else:
for _ in range(diff):
pB = pB.next
while pA:
if pA == pB:
return pA
pA = pA.next
pB = pB.next
return None
# 链表连接 + 双指针
# - 当两个指针指向同一个节点，表明有交集
# - 当两个指针都指向 None，表明无交集
# - time: O(m+n)
# - space: O(1)
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
pA, pB = headA, headB
while pA != pB:
if pA:
pA = pA.next
else:
pA = headB
if pB:
pB = pB.next
else:
pB = headA
return pA
ref
- https://neetcode.io/solutions/intersection-of-two-linked-lists
- https://www.youtube.com/watch?v=D0X0BONOQhI
todo 237. Delete Node in a Linked List
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
ListNode p = node.next;
node.val = p.val;
node.next = p.next;
}
}
287. Find the Duplicate Number
- 如果之前没遇到，大概率做不出来
- 这是一个linked list 问题 + Floyd’s
- 我放弃了
# sort
# - time: O(nlogn)
# - space: O(1)/O(n) depends on sorting algo
def findDuplicate(self, nums: List[int]) -> int:
nums.sort()
for i in range(len(nums) - 1):
if nums[i] == nums[i + 1]:
return nums[i]
return -1
# hashset
# - time: O(n)
# - space: O(n）
def findDuplicate(self, nums: List[int]) -> int:
seen = set()
for num in nums:
if num in seen:
return num
seen.add(num)
return -1
# slow fast pointers
# - time: O(n)
# - space: O(1）
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow, fast = 0, 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow2 = 0
while True:
slow = nums[slow]
slow2 = nums[slow2]
if slow == slow2:
return slow
ref
876. Middle of the Linked List
解题思路：
- 快慢指针，用两个指针
slow与fast一起遍历链表。slow一次走一步，fast一次走两步。那么当fast到达链表的末尾时，slow必然位于中间。 - 需要考虑包含奇数 or 偶数节点的两种情况
- 当有偶数个节点时，期待右边的节点为中间节点
# slow fast pointers
# - time: O(n)
# - space: O(1）
def middleNode(self, head):
"""
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
"""
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 当有偶数个节点时，期待左边的节点为中间节点，可以改成以下实现
def middleNode(self, head):
"""
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
"""
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
ref