Python中链表的反转指定区间内的节点操作
首先需要定义一个单向链表结构体，其中包括一个val表示节点的值，以及一个next表示下一个节点的指针。
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next
接着我们定义一个反转链表的函数，它接受链表的头节点head和尾节点tail，以及要反转的区间left和right，然后返回反转后的链表的头节点。
def reverse(head, tail): pre = tail.next p = head while pre != tail: next = p.next p.next = pre pre = p p = next return tail, head
最后我们使用一个迭代的方法来反转链表的指定区间。对于链表头节点为head，首先我们需要找到要反转区间的起点的前一个节点pre，以及反转区间的终点tail。
从pre开始反转，不断地将下一个节点插入到pre的后面，直到tail。这样反转后的链表就被连接到了原来的位置，我们只需要将pre的next指向反转后的链表的头节点即可。
def reverseBetween(head, left, right): if left == 1: pre = None else: pre = head for i in range(left-2): pre = pre.next # 找到区间的终点tail tail = head for i in range(right-1): tail = tail.next # 执行反转操作 node1, node2 = reverse(pre.next, tail) if pre: pre.next = node1 else: head = node1 node2.next = tail return head
下面是完整的代码演示：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse(head, tail): pre = tail.next p = head while pre != tail: next = p.next p.next = pre pre = p p = next return tail, head def reverseBetween(head, left, right): if left == 1: pre = None else: pre = head for i in range(left-2): pre = pre.next # 找到区间的终点tail tail = head for i in range(right-1): tail = tail.next # 执行反转操作 node1, node2 = reverse(pre.next, tail) if pre: pre.next = node1 else: head = node1 node2.next = tail return head # 构建一个链表，范例使用的是字符串pidancode.com head = ListNode('p') node1 = ListNode('i') node2 = ListNode('d') node3 = ListNode('a') node4 = ListNode('n') node5 = ListNode('c') node6 = ListNode('o') node7 = ListNode('d') node8 = ListNode('e') node9 = ListNode('.') head.next = node1 node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 node5.next = node6 node6.next = node7 node7.next = node8 node8.next = node9 # 反转区间[2,5] newHead = reverseBetween(head, 2, 5) # 打印反转后的结果 p = newHead while p: print(p.val, end='') p = p.next
输出结果为：
piandocde.
注意：以上代码均为Python 3.x版本，如果使用Python 2.x版本需要对部分语法进行调整。另外，本代码只是一种实现方式，不代表是最优解，读者可以根据自己的需求和理解来编写更加高效和灵活的代码。
相关文章