博客

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]



输出：[2,1,4,3]



示例 2：

输入：head = []



输出：[]



示例 3：

输入：head = [1]



输出：[1]

来源：力扣（LeetCode）



链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs

思路：

第一个想到的自然是链表两两一组交换，直到只剩下一个节点或没有节点，刚好用完为止。

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummyHead = ListNode(0)
        dummyHead.next = head
        temp = dummyHead
        while temp.next and temp.next.next:
            node1 = temp.next
            node2 = temp.next.next
            temp.next = node2
            node1.next = node2.next
            node2.next = node1
            temp = node1
        return dummyHead.next

当然，由于该题的循环次数也不确定，同样可以用递归的方式解决，其退出循环条件和迭代条件一样。

就直接摘官方代码了。

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        newHead = head.next
        head.next = self.swapPairs(newHead.next)
        newHead.next = head
        return newHead