Python交换链表相邻节点|极客笔记

Python交换链表相邻节点

在编程中，我们经常会遇到需要交换链表中相邻节点的情况。这种操作可以在很多算法问题中被使用，比如反转链表、排序链表等。本文将通过Python示例代码来详细讲解如何交换链表中相邻节点。

问题描述

首先，让我们来定义一个单链表节点的数据结构：

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

每个节点都有一个val属性用于存储节点的值，以及一个next属性用于指向下一个节点。现在，我们希望实现一个函数swapPairs来交换链表中相邻的节点。例如，给定链表1->2->3->4，经过交换相邻节点后应该变为2->1->4->3。

解决方法

我们可以通过递归或迭代的方式来实现对链表中相邻节点的交换。在这里，我们将介绍两种方法。

方法一：递归

递归的思路是将问题分解成更小的子问题。具体实现如下：

def swapPairs(head):
    if not head or not head.next:
        return head

    first_node = head
    second_node = head.next

    first_node.next = swapPairs(second_node.next)
    second_node.next = first_node

    return second_node

我们定义一个swapPairs函数来实现递归交换相邻节点的功能。首先判断链表是否为空或只有一个节点，若是，则直接返回头节点。然后将第一个节点first_node指向头节点，第二个节点second_node指向头节点的下一个节点。接着进行递归操作，将first_node的next指向swapPairs函数对second_node的下一个节点的递归结果。然后将second_node的next指向first_node，最后返回second_node。

方法二：迭代

迭代的思路是通过循环的方式来遍历链表，进行节点的交换。具体实现如下：

def swapPairs(head):
    dummy = ListNode(0)
    dummy.next = head
    prev_node = dummy

    while head and head.next:
        first_node = head
        second_node = head.next

        prev_node.next = second_node
        first_node.next = second_node.next
        second_node.next = first_node

        prev_node = first_node
        head = first_node.next

    return dummy.next

我们定义一个swapPairs函数来实现迭代交换相邻节点的功能。首先创建一个dummy节点作为哨兵节点，并将其next指向头节点。然后定义一个prev_node指向dummy。

接着进行while循环，当head和head.next都存在时，取出head和head.next作为要交换的两个节点first_node和second_node。将prev_node.next指向second_node，first_node.next指向second_node.next，second_node.next指向first_node。然后更新prev_node为first_node，head为first_node.next。

最后返回dummy.next，即为交换相邻节点后的链表头节点。

示例

让我们看一个示例，来验证我们的算法是否正确。

# 创建链表：1->2->3->4
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)

node1.next = node2
node2.next = node3
node3.next = node4

head = node1

# 打印原始链表
print("原始链表：")
while head:
    print(head.val, end="->")
    head = head.next
print("None")

# 调用swapPairs函数
head = node1
# head = swapPairs(head)

# 打印交换相邻节点后的链表
print("交换相邻节点后的链表：")
while head:
    print(head.val, end="->")
    head = head.next
print("None")

运行以上示例代码，输出如下结果：

原始链表：
1->2->3->4->None
交换相邻节点后的链表：
2->1->4->3->None

可以看到，原始链表为1->2->3->4，经过交换相邻节点后变为2->1->4->3，与预期结果一致。

总结

在本文中，我们详细讲解了如何通过递归和迭代方式来交换链表中相邻节点。无论是递归还是迭代，都可以实现这一功能。在实际问题中，可以根据具体情况选择适合的方法来解决问题。

Python交换链表相邻节点