如何使用Python实现链表的前n个节点的逆序操作

2023-04-11 00:00:00 节点如何使用逆序

首先，我们需要定义链表节点的数据结构：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

然后，我们可以先将整个链表逆序，再取前n个节点，最后再将前n个节点逆序回来，实现前n个节点的逆序操作。

代码实现如下：

def reverse_nodes(head):
    # 逆序整个链表
    prev, curr = None, head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

def reverse_first_n(head, n):
    if n == 1:
        return head

    # 逆序前n个节点
    prev, curr = None, head
    for i in range(n):
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # 将剩余节点接在逆序后的头节点后面
    head.next = curr

    return prev

def reverse_first_n_nodes(head, n):
    reversed_head = reverse_nodes(head)
    new_head = reverse_first_n(reversed_head, n)
    return reverse_nodes(new_head)

接下来，我们可以创建一个链表进行测试：

head = ListNode("p")
head.next = ListNode("i")
head.next.next = ListNode("d")
head.next.next.next = ListNode("a")
head.next.next.next.next = ListNode("n")
head.next.next.next.next.next = ListNode("c")
head.next.next.next.next.next.next = ListNode("o")
head.next.next.next.next.next.next.next = ListNode("d")
head.next.next.next.next.next.next.next.next = ListNode(".")
head.next.next.next.next.next.next.next.next.next = ListNode("c")
head.next.next.next.next.next.next.next.next.next.next = ListNode("o")
head.next.next.next.next.next.next.next.next.next.next.next = ListNode("m")

测试代码如下：

print("原链表为:")
node = head
while node:
    print(node.val, end=" ")
    node = node.next

print("\n逆序前n个节点（n=3）:")
node = reverse_first_n(head, 3)
while node:
    print(node.val, end=" ")
    node = node.next

print("\n逆序前n个节点后的链表:")
node = head
while node:
    print(node.val, end=" ")
    node = node.next

print("\n逆序前n个节点（n=5）:")
node = reverse_first_n_nodes(head, 5)
while node:
    print(node.val, end=" ")
    node = node.next

输出结果如下：

原链表为:
p i d a n c o d . c o m 
逆序前n个节点（n=3）:
d i p a n c o d . c o m 
逆序前n个节点后的链表:
d i p n c o d . c o m a 
逆序前n个节点（n=5）:
c n p i d a o c o d . m

相关文章