Swap every pair of nodes in a single linked list

This algorithm is just the extension of ‘swapping any two given nodes’ in a single linked list.

It can be done in two ways – #1 by swapping the addresses of each node #2 by swapping data of each node. #2 is straight forward and doesnt need any explanation. We will discuss #1 here.

Following diagram depicts what are we trying to do:

Let’s say Single Linked List is with 5 nodes n1,n2,n3,n4,n5
Analysis of the algorithm:
#1 – We swap two nodes as usual (n1 and n2 are swapped which leads to n2,n1,n3,n4,n5)
#2 – This is key step. before swapping next two nodes we should remember that n1’s next address should also be changed because when n3&n4 are swapped n1->n3 link will be broken and hence we should take care of this step. (n3 and n4 are swapped and n1’s next is linked to n4 – which leads to n2,n1,n4,n3,n5)

Source Code

	public static Node swap(Node n) {
		Node buffer = null;
		Node newRoot = null;
		while (n != null && n.next != null) {
			if (buffer != null) {
				buffer.next.next = n.next;
			}

			buffer = n.next;
			n.next = n.next.next;
			buffer.next = n;
			if (newRoot == null)
				newRoot = buffer;
			n = n.next;
		}
		return newRoot;
	}