Swap Nodes In Pairs

两两交换链表的节点

题目描述

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

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

示例：

输入：1 -> 2 -> 3 -> 4
输出：2 -> 1 -> 4 -> 3

解法

方法一：递归

• 时间复杂度：O(n)

• 空间复杂度：O(n)

func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    first := head
    second := head.Next

    first.Next = swapPairs(second.Next)
    second.Next = first
    return second
}

方法二：迭代

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    tmp := dummy

    for tmp.Next != nil && tmp.Next.Next != nil {
        first := tmp.Next
        second := first.Next

        first.Next = second.Next
        second.Next = first
        tmp.Next = second

        tmp = first
    }

    return dummy.Next
}