Solving the LeetCode "Swap Nodes in Pairs" Problem in Go

Difficulty: Medium | Tags: Linked List, Recursion

Introduction

This problem requires swapping every two adjacent nodes in a linked list without modifying the node values. It tests your understanding of linked list manipulation and recursion.

Problem Analysis

Given a linked list, we need to swap every pair of adjacent nodes. For example, [1,2,3,4] becomes [2,1,4,3]. The challenge is to perform this operation in-place, modifying only the node pointers.

Solution Approach

We can solve this problem using either an iterative or recursive approach. The iterative method involves traversing the list while maintaining pointers to the previous, current, and next nodes. The recursive approach breaks the problem into smaller subproblems by recursively swapping the remaining list after the first pair.

Go Implementation

/**
* Definition for singly-linked list.
* type ListNode struct {
    *     Val int
    *     Next *ListNode
    * }
    */
    func swapPairs(head *ListNode) *ListNode {
        // Base case: empty list or single node
        if head == nil || head.Next == nil {
            return head
        }
        // Nodes to be swapped
        firstNode := head
        secondNode := head.Next
        // Swap the pair and recursively process the remaining list
        firstNode.Next = swapPairs(secondNode.Next)
        secondNode.Next = firstNode
        // New head after swap
        return secondNode
    }

Complexity Analysis

Time Complexity: O(n) - We visit each node exactly once.
Space Complexity: O(n) - The recursion stack can go up to n/2 levels deep in the worst case.

Testing and Examples

Test cases should cover:
1. Empty list ([] → [])
2. Single node ([1] → [1])
3. Even number of nodes ([1,2,3,4] → [2,1,4,3])
4. Odd number of nodes ([1,2,3] → [2,1,3])

Best Practices and Tips

1. Always handle edge cases (empty list or single node) first.
2. For iterative solutions, use dummy nodes to simplify pointer manipulation.
3. Draw diagrams to visualize pointer changes before coding.
4. Consider both recursive and iterative approaches for linked list problems.