Problem

Given a single Linked List. Swap every other alternate nodes.

Examples

Example 1:

Input: head = 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 3 -> 4 -> 5 -> 1 -> 2 -> null
Explanation: The list was transformed in several steps.

1. First step, swap 1 and 3 i.e. 3–>2–>1–>4–>5–>null
2. Second step, swap 2 and 4 i.e. 3–>4–>1–>2–>5–>null
3. last step, swap 1 and 5, i.e. 3–>4–>5–>2–>1–>null

Similar Problems

Solution

Method 1 - Reverse 3 nodes at a time

We can observe that each step involves reversing a sublist of size 3 starting from the current node and then advancing the head to the next node for the subsequent iteration. Reversing a 3-element linked list is straightforward and can be achieved with just two swaps (or by using two temporary variables). The most challenging aspect of this problem is maintaining the correct pointer to the head of the list. Below is a simple yet effective implementation.

Code

Java
public ListNode swapAlternateNodes(final ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode newhead = null;
    ListNode prev = head;
    ListNode cur = prev.next;
    ListNode temp = null;
    ListNode lastTemp = null;
    while (cur != null && cur.next != null) {
        temp = cur.next;

        prev.next = cur.next.next;
        cur.next = prev;
        temp.next = cur;

        if (newhead == null) {
            newhead = temp;
        } else {
            lastTemp.next = temp;
        }

        prev = cur;
        cur = cur.next;
        lastTemp = temp;
    }

    return newhead;
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the list.
  • 🧺 Space complexity: O(1)