Puzzle
Given an Unordered 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 -> 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()
{
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.
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.
| Reference: | Coding: Reversing Unordered Single Linked List using 2 Pointers from our JCG partner Paolo Maresca at the TheTechSolo blog. |
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 »
I think that’s supposed to be a four not a five…
Hi James,
you’re right, that’s a typo that I fixed on the blog. The output (as in the picture) is ‘0 -> 2 -> 3 -> 4 -> 1’.
Thanks for pointing this out!
Cheers,
P