Problem
Reverse a singly linked list in linear time complexity.
Solution
- Traverse through the list once and for each node assign the next pointer to the previous node.
- Time complexity O(n).
- Java based implementation along with unit test below
package com.computepatterns.problemsolving.linkedlist;
/**
* Reverse the singly linked list.
* Time complexity - Linear - O(n). Just one loop and reassign pointers for every node to the previous node.
*/
public class ReverseSinglyLinkedList {
/**
* Represents nodes in the linked list.
*/
public static class Node{
private int value;
private Node next;
public Node(int value) {
this.value = value;
}
public int getValue() {
return value;
}
Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
private Node start;
public void setStart(Node start) {
this.start = start;
}
/**
* Creates string representing the sequence of the content of the list delimite by coma.
*/
public String createStringRepresentation(Node start){
Node currentNode = start;
StringBuilder toPrint = new StringBuilder();
while(null != currentNode){
toPrint.append(currentNode.getValue() + ",");
currentNode = currentNode.next;
}
return toPrint.toString();
}
/**
*
* @return Head of the revised linked
*/
public Node reverse(){
Node previous = null;
Node next = null;
Node current = start;
while(null != current){
next = current.getNext();
current.next = previous;
previous = current;
current = next;
}
return previous;
}
}
package com.computepatterns.problemsolving.linkedlist;
import org.junit.Test;
import static org.junit.Assert.*;
/**
* Test reverse linked list.
*/
public class ReverseSinglyLinkedListTest {
private ReverseSinglyLinkedListTest linkedList;
@Test
public void testReverse() throws Exception {
ReverseSinglyLinkedList linkedList = new ReverseSinglyLinkedList();
ReverseSinglyLinkedList.Node node1 = new ReverseSinglyLinkedList.Node(1);
ReverseSinglyLinkedList.Node node2 = new ReverseSinglyLinkedList.Node(2);
ReverseSinglyLinkedList.Node node3 = new ReverseSinglyLinkedList.Node(3);
ReverseSinglyLinkedList.Node node4 = new ReverseSinglyLinkedList.Node(4);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
linkedList.setStart(node1);
// Before reversing.
System.out.println(linkedList.createStringRepresentation(node1));
// Find middle element.
ReverseSinglyLinkedList.Node startOfReversed = linkedList.reverse();
// After reversing.
String stringRepresentation = linkedList.createStringRepresentation(startOfReversed);
System.out.println(stringRepresentation);
assertEquals("4,3,2,1,", stringRepresentation);
}
}