/* reverse head -> 1 -> 2 -> 3 -> 4 to head -> 4 -> 3 -> 2 -> 1
*
* recursive
*
* given a linked list 1 -> 2 -> 3 -> 4,
* we follow the following steps:
* step 1. reverse the nodes other than the first one.
* change 1 -> 2 -> 3 -> 4 to 1 ->* 4 -> 3 -> 2*
* step 2. add the first node to the tail of the reversed sub linked list
* change 1 -> 2 -> 3 -> 4 to 4 -> 3 -> 2 -> 1
*
* The reverse method traversals the linked list once,
* the time complexity is O(N).
*
* This solution need to recursively call itself, the calling stack will take extra space
* the space complexity is similar to SolutionOne, which is O(N).
*
*
* */
public class SolutionThree {
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);
}
/*
* special treatment for the linked list with head node.
* */
public static MyNode reverse(MyNode head) {
if(head == null) return head;
//get first node
MyNode first = head.next;
//reverse the linked list
MyNode newHead = recursivereverse(first);
//point the head to the first node of the reversed linked list
head.next = newHead;
return head;
}
/*
* reverse the sub linked list that do not contain the original head node
* */
public static MyNode recursivereverse(MyNode head) {
//empty linked list or one element linked list
if(head == null || head.next == null) {
return head;
} else {
//reverse the nodes following the current node.
MyNode newHead = recursivereverse(head.next);
//once the nodes are reversed, point its tail to the current node
head.next.next = head;
//the last node should point nowhere
head.next = null;
//return the first node of the reversed sub linked list
return newHead;
}
}
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;
}
}
