Swap alternate nodes in a singly linked list

Posted on by

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. Note that, 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

We can observe that, each step it is reversing the linked list of size 3 from current node and moving the head to next node for next step. Reversing a 3 element linked list is pretty simple using two swaps (or using 2 temp variables). The hardest part of this problem is to maintain the head of the list. Here is a simple but working code.

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.

ublic 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;
}

 

Bonus Question: Delete List Nodes With Larger Value Node On Right

Given a single linked list. Delete all the elements that has lager value element on right of it.

public static ListNode deleteNodeWithHighOnRight(ListNode head){
	ListNode temp = null;
	ListNode newHead = null;
	ListNode prev = head;
	while(head != null && head.next != null){
		temp = head.next;
		
		if(temp.val > head.val){
			prev.next = temp;
		}
		else {
			if(newHead == null){
				newHead = head;
			}
			prev = head;
		}
		
		head = head.next;
	}
	
	return newHead;
}