Python算法
链表算法实战：反转、合并与排序（Python）
链表算法实战涵盖基础反转、区间反转及分组翻转。通过快慢指针定位中间节点实现归并排序，结合双指针合并有序链表完成整体排序。提供 Python 代码示例，包含哨兵节点优化逻辑，解决 LeetCode 经典链表问题。
链表算法实战涵盖基础反转、区间反转及分组翻转。通过快慢指针定位中间节点实现归并排序，结合双指针合并有序链表完成整体排序。提供 Python 代码示例，包含哨兵节点优化逻辑，解决 LeetCode 经典链表问题。
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
cur = head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
整体来看，p0 是反转前的第 left 个节点的前驱，pre 是反转后的头节点，cur 是当前遍历到的节点。
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
p0 = dummy = ListNode(next=head)
for _ in range(left - 1):
p0 = p0.next
pre = None
cur = p0.next
for _ in range(right - left + 1):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
p0.next.next = cur
p0.next = pre
return dummy.next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
n = 0
cur = head
while cur:
n += 1
cur = cur.next
p0 = dummy = ListNode(next=head)
pre = None
cur = head
while n >= k:
n -= k
for _ in range(k):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
nxt = p0.next
nxt.next = cur
p0.next = pre
p0 = nxt
return dummy.next
典型的快慢指针法。t1 每次走一步，t2 每次走两步，当 t2 到达末尾时，t1 即为中间节点。
class 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
class Solution:
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
cur = cur.next
list1 = list1.next
else:
cur.next = list2
cur = cur.next
list2 = list2.next
cur.next = list1 if list1 else list2
return dummy.next
归并排序。找到链表的中间节点，断开为前后两端，分别排序前后两端，排序后再合并两个有序链表。
class Solution:
# 876. 链表的中间结点（快慢指针）
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None
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.next
else:
cur.next = 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 = self.middleNode(head)
head = self.sortList(head)
head2 = self.sortList(head2)
return self.mergeTwoLists(head, head2)
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online