Software Development

# Coding: Reversing Unordered Single Linked List using 2 Pointers

## Puzzle

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

Input

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

Output

`Example. 0 -> 5 -> 3 -> 2 -> 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()
{
return;

Node p1 = head, p2 = p1.next, tmp = null;
p1.next = null;
while(p1 != p2) { // reverse links incrementally
if(p2.next == null) {
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.

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()
{
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) {
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.

 Reference: Coding: Reversing Unordered Single Linked List using 2 Pointers from our JCG partner Paolo Maresca at the TheTechSolo blog.

### Paolo Maresca

Paolo is a Sr Software Engineer with a diversified experience in the ICT Industry. He is a passionate and committed Distributed Systems Engineer that daily tries to put the bar higher. He is polyglot: he masters Java SE/EE, C/C++, Python, JavaScript, Bash and he is getting proficient with Scala. He is PC member of international conferences like IEEE and IARIA. He blogs. He is an independent thinker!
Subscribe
Notify of

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Inline Feedbacks
jabbarish
8 years ago

package listreverse; public class List { private static class Node { public Node(V item, Node next) { value = item; this.next = next; } Node next; V value; } Node head; Node last; public void add(T item) { Node x = new Node(item, null); if (last == null) { head = x; } else { last.next = x; } last = x; } void print() { System.out.println(“—“); Node ptr = head; while (ptr != null) { System.out.println(ptr.value); ptr = ptr.next; } } void reverse() { last = head; head = null; Node next; while (true) { next = last.next; last.next… Read more »

James
8 years ago

I think that’s supposed to be a four not a five…

8 years ago