leetcode-24

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

class Solution:
    '''
    官方题解1：递归
    '''
    def swapPairs1(self, head: ListNode) -> ListNode:
        
        '''如果现在是最后一个节点'''
        if not head or not head.next:
            return head
        
        newHead = head.next # 新指针指向当前的下一个
        head.next = self.swapPairs1(newHead.next) # 开始遍历第3个
        newHead.next = head # 新指针的下一个指向当前
        return newHead
    
    '''
    官方题解2：迭代
    '''
    def swapPairs2(self,head:ListNode) -> ListNode:
        dummyHead = ListNode(0)
        dummyHead.next = head
        temp = dummyHead

        '''temp作为当前节点，交换temp后面的两个节点'''
        while temp.next and temp.next.next:
            node1 = temp.next # 第一个节点
            node2 = temp.next.next # 第二个节点

            temp.next = node2 # 当前节点指向第2个节点
            node1.next = node2.next # 第一个节点指向第2个节点的后面
            node2.next = node1 # 第二个节点指向第一个节点的后面

            temp = node1 # 当前节点移到现在的第二个节点上
        return dummyHead.next

官方解法一：递归

递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。

链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换.

官方解法二：迭代

先创建一个哑结点，作为头结点。

令 temp 表示当前到达的节点，初始时 temp = dummyHead。每次需要交换 temp 后面的两个节点。

具体而言，交换之前的节点关系是 temp -> node1 -> node2，交换之后的节点关系要变成 temp -> node2 -> node1，因此需要进行如下操作。

判断条件是temp的后面两个节点不为空。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。