Python中链表的反转链表 II 操作
反转链表 II 操作是指从链表的第 m 个元素到第 n 个元素的部分反转，其余部分保持原样。例如，给定链表 1->2->3->4->5，m=2，n=4，则返回链表 1->4->3->2->5。
实现该操作的关键在于如何找到需要反转的链表区间，并把这个区间内的链表反转。具体实现中，需要用两个指针（pre 和 cur）来遍历链表，找到第 m 个节点的前面一个节点（pre），以及第 m 个节点（cur）。此时需要记录下 pre.next 和 cur.next，以便在反转链表区间时顺利重新连接链表。然后再用一个指针（temp）从 cur 开始向后遍历，将每个节点插入到 pre 和 cur 之间（类似于插入排序的思想），直至遍历到 n 个节点为止。
下面是 Python 代码实现：
class ListNode: def __init__(self, x): self.val = x self.next = None def reverseBetween(head, m, n): if not head or not head.next: return head # 添加 dummy 节点，方便处理头部的情况 dummy = ListNode(0) dummy.next = head pre = dummy # 找到第 m 个节点的前面一个节点 for i in range(m-1): pre = pre.next cur = pre.next # 反转链表区间 for i in range(n-m): temp = cur.next cur.next = temp.next temp.next = pre.next pre.next = temp return dummy.next
下面是对代码的调用示例：
# 构造链表 1 -> 2 -> 3 -> 4 -> 5 head = ListNode(1) head.next = ListNode(2) head.next.next = ListNode(3) head.next.next.next = ListNode(4) head.next.next.next.next = ListNode(5) # 反转链表区间 [2, 4] new_head = reverseBetween(head, 2, 4) # 遍历链表并打印结果 while new_head: print(new_head.val, end=" ") new_head = new_head.next # 输出: 1 4 3 2 5
相关文章