/* reverse head -> 1 -> 2 -> 3 -> 4 to head -> 4 -> 3 -> 2 -> 1
*
* reverse by inserting node behind head
*
* traversal the linked list, remove the current node,
* insert it behind the head node.
*
* change head -> 1 -> 2 -> 3 -> 4
* to head -> 1 -> 2 -> 3 -> 4
* then head -> 2 -> 1 -> 3 -> 4
* then head -> 3 -> 2 -> 1 -> 4
* then head -> 4 -> 3 -> 2 -> 1
*
* The reverse method traversals the linked list once,
* the time complexity is O(N).
*
* This solution didn't create a new linked list,
* the space complexity is O(1).
*
* */
public class SolutionFive {
public static MyNode reverse(MyNode head) {
if(head == null || head.next == null) return head;
MyNode current = head.next;
MyNode next = null;
while(current.next != null) {
next = current.next;
current.next = current.next.next;
next.next = head.next;
head.next = next;
}
return head;
}
public static void main(String...args) {
MyNode head = createLinkedList();
MyNode preHead = new MyNode(0, head.next);
printResult(head);
head = reverse(head);
printResult(head);
printResult(preHead);
}
public static void printResult(MyNode head) {
if(head == null) return;
MyNode current = head;
System.out.println();
while (current.next != null) {
current = current.next;
System.out.print(current.value + " ");
}
}
public static MyNode createLinkedList() {
MyNode head = new MyNode(0, null);
MyNode next = new MyNode(1, null);
head.next = next;
next.next = new MyNode(2, null);
next = next.next;
next.next = new MyNode(3, null);
next = next.next;
next.next = new MyNode(4, null);
next = next.next;
next.next = new MyNode(5, null);
next = next.next;
next.next = new MyNode(6, null);
next = next.next;
return head;
}
}
