Data Structures and Algorithms · Programming Languages · Software Engineering

Coding: Reversing Unordered Single Linked List using 2 Pointers

Coding
Keep Calm… and, Try Coding

Puzzle

Given an Unsorted Single Linked List, provide an Algorithm to reverse such Linked List using only 2 pointers.

Input

A Single Linked List.

Example. 1 -> 4 -> 3 -> 2 -> 0

Output

A Reversed Single Linked List.

Example. 0 -> 2 -> 3 -> 4 -> 1

 

Solution Using Java as Programming Language

Complete Code Base is spread on 3 Gist snippets, as follows

  • Abstract Class defining the Unsorted Linked List ADT and implementing banal methods,
  • Implementation Class defining the business logic for the Unsorted Linked List,
  • Test Class defining the suite of test cases for the Unsorted Linked List ADT implementation.

Hereafter, an extract of the code to show up how to realize the assignment using an iterative approach.

public void iterativeReverse()
{
if(head == null || head.next == null)
return;

Node p1 = head, p2 = p1.next, tmp = null;
p1.next = null;
while(p1 != p2) { // reverse links incrementally
if(p2.next == null) {
head = p2;
tmp = null;
} else
tmp = p2.next;
p2.next = p1;
p1 = p2;
if(tmp != null)
p2 = tmp;
}
}

How does the Algorithm evolve? Well, looking at the following diagram everything should be clear.

ReverseUnsortedLinkedList
Reverse Unsorted Linked List

As intuitive, the same problem can be solved using recursion; hereafter an extract of the code that shows up how to approach the solution using recursion.


public void recursiveReverse()
{
if(head == null || head.next == null)
return;

Node p1 = head, p2 = p1.next;
p1.next = null;
_reverse(p1, p2); // reverse recursively
}

private void _reverse(Node p1, Node p2)
{
if(p2.next == null) {
head = p2;
p2.next = p1;
p1 = p2;
} else {
Node tmp = p2.next;
p2.next = p1;
p1 = p2;
p2 = tmp;
_reverse(p1, p2);
}
}

Discussion

The main idea consists in reversing the pointers incrementally. As clear from the proposed diagram, two additional pointers aid in scanning through the overall Unsorted Single Linked List, and one pointer at time the inversion operation is accomplished. From the code, some corner cases have to be taken into consideration; for instance, the first operation on pointer one (i.e p1 in the picture, when it points to the head of the list) has to nullify the pointer to next for obvious reasons: p2 will point back to p1, so p1 pointing to p2 would create a loop. On the other hand, p2 has to be moved until the temporary placeholder is different from null: this will create the situation in which at the end of the processing p1 and p2 will point to the same tail element. Such condition (i.e. p1 equals p2, that in turn is equal to the tail of the list) represents the termination check.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s