Swap alternate nodes in a singly linked list - Algorithms and Problem SolvingAlgorithms and Problem Solving

Swap alternate nodes in a singly linked list - Algorithms and Problem SolvingAlgorithms and Problem Solving

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

For example, given 1–>2–>3–>4–>5–>null then output 3–>4–>5–>2–>1–>null.

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

    LinkedListNode newhead = null;
    LinkedListNode prev = head;
    LinkedListNode cur = prev.next;
    LinkedListNode temp = null;
    LinkedListNode 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;
}

Sometimes this problem is confused with another problem of swapping alternate pair of elements which will transform 1–>2–>3–>4–>5–>null into 2–>1–>4–>3–>5–>null. This one is pretty simple as we are swapping 2 elements each step.

public static LinkedListNode swapPairNodes(LinkedListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    LinkedListNode newHead = null;
    LinkedListNode cur = head;
    LinkedListNode prev = null;
    LinkedListNode temp = null;
    while (cur != null && cur.next != null) {
        temp = cur.next;
        cur.next = cur.next.next;
        temp.next = cur;
        if (prev != null) {
            prev.next = temp;
        }

        if (newHead == null) {
            newHead = temp;
        }

        prev = cur;
        cur = cur.next;
    }

    head = newHead;
    return newHead;
}

Read full article from Swap alternate nodes in a singly linked list - Algorithms and Problem SolvingAlgorithms and Problem Solving