leetcode(12)链表系列题目
21. 合并两个有序链表
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
if list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
23. 合并K个升序链表
思路 1：
归并，分而治之
链表两两合并
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists:
return
n = len(lists)
return self.merge(lists, 0, n - 1)
def merge(self, lists, left, right):
if left == right:
return lists[left]
mid = (left + right) // 2
l = self.merge(lists, left, mid)
r = self.merge(lists, mid + 1, right)
return self.mergeTwo(l, r)
def mergeTwo(self, l1, l2):
if not l1:
return l2
if not l2:
return l1
if l1.val < l2.val:
l1.next = self.mergeTwo(l1.next, l2)
return l1
else:
l2.next = self.mergeTwo(l1, l2.next)
return l2
思路 2：
调用优先级队列，实现最小堆
时间复杂度：O(n?log(k))，n 是所有链表中元素的总和，k 是链表个数。
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
import heapq #调用堆
minHeap = []
for l in lists:
while l:
heapq.heappush(minHeap, l.val) #把l中的数据逐个加到堆中
l = l.next
dummy = ListNode(0)
p = dummy #构造虚节点
while minHeap:
val = heapq.heappop(minHeap) #依次弹出最小堆的数据
p.next = ListNode(val)
p = p.next
return dummy.next
206.反转链表
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre, cur = None, head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
25. K 个一组翻转链表
注意：与 206.反转链表 的区别是需要判断节点是否够K个一组，并且要递归的调用翻转
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
cur = head
for _ in range(k):
if not cur:
return head # 如果head后续节点数不足k个直接返回head
cur = cur.next
pre, cur = None, head
for _ in range(k): # 将包括head往后的k个节点翻转
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
head.next = self.reverseKGroup(cur, k) # 递归得到下一段k个节点的反转后的头结点
# head已经是当前段k个节点的尾节点了，指向下一段的反转后的头结点
return pre
24. 两两交换链表中的节点
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
res = ListNode(next = head)
pre = res
while pre.next and pre.next.next:
cur = pre.next
tmp = pre.next.next
cur.next = tmp.next
tmp.next = cur
pre.next = tmp
pre = pre.next.next
return res.next
92. 反转链表 II
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
# 设置 dummyNode 是这一类问题的一般做法
# dummy = ListNode(-1)
# dummy.next = head
dummy = ListNode(next = head) # 等价于
pre = dummy
for _ in range(left - 1):
pre = pre.next
cur = pre.next
for _ in range(right - left):
next = cur.next
cur.next = next.next
next.next = pre.next
pre.next = next
return dummy.next
876. 链表的中间结点
双指针
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
if not head:
return head
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
143. 重排链表
简洁代码，取中，翻转，合并
class Solution:
def reorderList(self, head: ListNode) -> None:
if not head:
return
# 找到中点
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 翻转后半
pre, cur = None, slow.next
slow.next = None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
# 交替合并
left, right = head, pre
while right:
tmp = left.next #注意这里是left.next
left.next = right
left = right
right =tmp
19. 删除链表的倒数第 N 个结点
141. 环形链表
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
142. 环形链表 II
相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：
(x + y) * 2 = x + y + n (y + z)
两边消掉一个（x+y）: x + y = n (y + z)
因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。
所以要求x ，将x单独放在左面：x = n (y + z) - y ,
再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。
当 n为1的时候，公式就化解为 x = z，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。
即从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
p = head
q = slow
while p != q:
p = p.next
q = q.next
return p
return None