双指针
在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针。
所谓左右指针，就是两个指针相向而行或者相背而行；而所谓快慢指针，就是两个指针同向而行，一快一慢。
对于单链表来说，大部分技巧都属于快慢指针，比如链表环判断，倒数第 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
解析
21. Merge Two Sorted Lists
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
p = dummy
while list1 and list2:
if list1.val < list2.val:
p.next = list1
list1 = list1.next
else:
p.next = list2
list2 = list2.next
p = p.next
if list1:
p.next = list1
else:
p.next = list2
return dummy.next
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
141. Linked List Cycle
-
判断链表中是否有环，可以用快慢指针，如果有环，快慢指针一定会相遇
-
ref