Python中链表的两两交换节点的优化算法

2023-04-11 00:00:00 算法节点链表

链表两两交换节点的一般思路是，定义三个指针pre、cur和next，分别指向相邻节点的前一个节点、当前节点和后一个节点，然后进行交换操作。但是这种方法需要考虑很多边界情况，比较繁琐。

一种更简洁的方法是采用递归实现。具体来说，假设要交换的两个节点分别为head和next，交换后head成为next的后继节点，而next成为head的前驱节点。递归地对下一组节点进行交换，将其返回的结果接到head后面即可。

下面是Python代码演示：

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

def swapPairs(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    next = head.next
    head.next = swapPairs(next.next)
    next.next = head
    return next

# 测试代码
def printList(head: ListNode):
    while head:
        print(head.val, end=" ")
        head = head.next
    print()

head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
printList(head) # 1 2 3 4
head = swapPairs(head)
printList(head) # 2 1 4 3

在上面的代码中，swapPairs函数通过递归方式交换相邻节点，并将交换后的链表返回给调用者。如果链表长度为偶数，则每两个相邻节点会被交换一次；如果长度为奇数，则最后一个节点不参与交换。

相关文章