力扣hot100_链表(3)_python版本

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

1.1、206. 反转链表

• py代码

classListNode:def__init__(self, val=0,next= node): self.val = val self.next=nextclassSolution:defreverseList(self, head): pre =None cur = head while cur:next= cur.next cur.next= pre pre = cur cur =nextreturn pre 

1.2、92. 反转链表 II

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

classSolution:defreverseBetween(self, head, left, right): p0 = dummy = ListNode(next= head)# 这样一起实例化，p0和dummy永远都是指向同一位置for _ inrange(left-1): p0 = p0.next# 知道转换的前一个结点 pre =None cur = p0.next# 当前正在处理的节点for _ inrange(right-left+1) nxt = cur.next cur.nxt = pre pre = cur cur = nxt p0.next.next= cur p0.next= pre return dummy.next

• 代码：

classSolution:defreverseKGroup(self, head, k): n =0 cur = head while cur: n +=1 cur = cur.next p0 = dummy = ListNode(next= head) pre =None cur = head # k个一组处理while n >= k: n -= k for _ inrange(k): nxt = cur.next cur.next= pre pre = cur cur = nxt nxt = p0.next nxt.next= cur p0.next= pre p0 = nxt 

二、148. 排序链表

2.1、876. 链表的中间结点

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

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

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

• 代码：

classSolution:defmergeTwoLists(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.nextelse: cur.next= list2 cur = cur.next list2 = list2.nextif list1: cur.next= list1 else: cur.next= list2 return dummy.next

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

classSolution:# 876. 链表的中间结点（快慢指针）defmiddleNode(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. 合并两个有序链表（双指针）defmergeTwoLists(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.nextelse:# 注：相等的情况加哪个节点都是可以的 cur.next= list2 # 把 list2 加到新链表中 list2 = list2.next cur = cur.next cur.next= list1 if list1 else list2 # 拼接剩余链表return dummy.nextdefsortList(self, head: Optional[ListNode])-> Optional[ListNode]:# 如果链表为空或者只有一个节点，无需排序if head isNoneor head.nextisNone: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)