力扣hot100_链表(3)_python版本

一、25. K 个一组翻转链表

1.1、206. 反转链表

• py代码

class ListNode:def __init__(self, val=0, next= node):self.val = valself.next = nextclass Solution:def reverseList(self, head):pre = Nonecur = headwhile cur:next = cur.nextcur.next = prepre = curcur = nextreturn pre

1.2、92. 反转链表 II

• 思路：
  整体来看，1是反转前的第left个节点（p0.next），pre（4）是反转的后的头节点，cur是当前遍历到的节点下一个（5）。

class Solution:def reverseBetween(self, head, left, right):p0 = dummy = ListNode(next = head) # 这样一起实例化，p0和dummy永远都是指向同一位置for _ in range(left-1):p0 = p0.next # 知道转换的前一个结点pre = Nonecur = p0.next # 当前正在处理的节点for _ in range(right-left+1)nxt = cur.nextcur.nxt = prepre = curcur = nxtp0.next.next = curp0.next = prereturn dummy.next

• 代码：

class Solution:def reverseKGroup(self, head, k):n = 0cur = headwhile cur:n += 1cur = cur.nextp0 = dummy = ListNode(next = head)pre = Nonecur = head# k个一组处理while n >= k:n -= kfor _ in range(k):nxt = cur.nextcur.next = prepre = curcur = nxtnxt = p0.nextnxt.next = curp0.next = prep0 = nxt

二、148. 排序链表

2.1、876. 链表的中间结点

• 代码：这道题典型的快慢指针

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: t1 = t2 = head while t2 and t2.next: t1 = t1.next t2 = t2.next.next return t1

2.2、21. 合并两个有序链表

• 代码：

class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() cur = dummy while list1 and list2: if list1.val <= list2.val: cur.next = list1 cur = cur.next list1 = list1.next else: cur.next = list2 cur = cur.next list2 = list2.next if list1: cur.next = list1 else: cur.next = list2 return dummy.next

• 思路1：归并排序
  找到链表的中间节点，断开为前后两端，分别排序前后两端，排序后，再合并两个有序链表。
• 代码1：

class Solution: # 876. 链表的中间结点（快慢指针） def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: slow = fast = head while fast and fast.next: pre = slow # 记录 slow 的前一个节点 slow = slow.next fast = fast.next.next pre.next = None # 断开 slow 的前一个节点和 slow 的连接 return slow # 21. 合并两个有序链表（双指针） def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: cur = dummy = ListNode() # 用哨兵节点简化代码逻辑 while list1 and list2: if list1.val < list2.val: cur.next = list1 # 把 list1 加到新链表中 list1 = list1.next else: # 注：相等的情况加哪个节点都是可以的 cur.next = list2 # 把 list2 加到新链表中 list2 = list2.next cur = cur.next cur.next = list1 if list1 else list2 # 拼接剩余链表 return dummy.next def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: # 如果链表为空或者只有一个节点，无需排序 if head is None or head.next is None: return head # 找到中间节点 head2，并断开 head2 与其前一个节点的连接 # 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3] head2 = self.middleNode(head) # 分治 head = self.sortList(head) head2 = self.sortList(head2) # 合并 return self.mergeTwoLists(head, head2)