24. Swap Nodes in Pairs

Description

Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list’s nodes. Only nodes itself may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [1]
Output: [1]

Constraints:

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100.

Solutions

I Iteration

Complexity:

• Time complexity: \(O(n)\).
• Space complexity: \(O(1)\).

type ListNode struct {
    Val  int
    Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}
    p := dummy

    for p.Next != nil && p.Next.Next != nil {
        pairA, pairB := p.Next, p.Next.Next

        pairA.Next = pairB.Next
        pairB.Next = pairA
        p.Next = pairB
        p = pairA
    }

    return dummy.Next
}