Skip to content

Instantly share code, notes, and snippets.

@flexelem
Created June 13, 2014 10:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save flexelem/e21a8276243c835992b4 to your computer and use it in GitHub Desktop.
Save flexelem/e21a8276243c835992b4 to your computer and use it in GitHub Desktop.
Reverse a LinkedList
public class LinkedList {
public class Node {
int data;
Node next;
public Node(int item) {
this.data = item;
}
}
public Node head;
public void insert(int item) {
if (head == null) {
head = new Node(item);
return;
}
Node currentNode = head;
while (currentNode.next != null) {
currentNode = currentNode.next;
}
currentNode.next = new Node(item);
}
public void print() {
Node curr = head;
while (curr != null) {
System.out.println(curr.data);
curr = curr.next;
}
}
}
import linkedlist.LinkedList.Node;
public class ReverseLinkedList {
public void reverseLinkedList(LinkedList list) {
boolean firstReverse = true;
Node prev = null;
Node current = null;
Node next = null;
prev = list.head;
current = prev.next;
next = current.next;
while (next != null) {
current.next = prev;
if (firstReverse) {
prev.next = null;
firstReverse = false;
}
prev = current;
current = next;
next = next.next;
}
// tie the last node and make it head
current.next = prev;
list.head = current;
}
}
import linkedlist.LinkedList.Node;
import org.junit.Before;
import org.junit.Test;
public class ReverseLinkedListTest {
private ReverseLinkedList testClass;
private LinkedList list;
@Before
public void setUp() {
testClass = new ReverseLinkedList();
list = new LinkedList();
init();
}
@Test
public void testName() {
testClass.reverseLinkedList(list);
Node current = list.head;
while (current != null) {
System.out.print(current.data + " --> ");
current = current.next;
}
}
private void init() {
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);
list.insert(5);
list.insert(6);
list.insert(7);
list.insert(8);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment