algoadvance

Leetcode 24. Swap Nodes in Pairs

Problem Statement

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed).

For example:

Clarifying Questions

  1. Q: What happens if there’s an odd number of nodes in the linked list?
    • A: The last node remains as it is since there is no adjacent node to swap with.
  2. Q: Can the linked list be empty?
    • A: Yes, in the case of an empty list, the result should also be an empty list.
  3. Q: What is the range of the number of nodes in the list?
    • A: There can be anywhere from 0 to 100 nodes.
  4. Q: Can we use additional data structures to assist with the solution?
    • A: No, the challenge here is to swap the nodes themselves without using extra space beyond the stack frame in a recursive solution.

Strategy

  1. Iterative Approach:
    • Use a dummy node that simplifies edge cases.
    • Traverse the list in pairs and swap nodes.
    • Update pointers accordingly to swap adjacent nodes.
  2. Recursive Approach:
    • Base case: If there are fewer than two nodes left, return the head.
    • Recursive case: Swap the first two nodes and recursively solve for the rest of the list.

Code

Iterative Approach:

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;

        while (current.next != null && current.next.next != null) {
            ListNode first = current.next;
            ListNode second = current.next.next;

            // swap
            first.next = second.next;
            second.next = first;
            current.next = second;

            // move current
            current = first;
        }

        return dummy.next;
    }
}

Recursive Approach:

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode first = head;
        ListNode second = head.next;

        first.next = swapPairs(second.next);
        second.next = first;

        return second;
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI