/* reverse linked list 1 -> 2 -> 3 -> 4 to 4 -> 3 -> 2 -> 1
* notice there is no head node
*
* 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 ExtendSolutionThree {
public static MyNode reverse(MyNode head) {
if(head == null || head.next == null) return head;
MyNode sub = reverse(head.next);
//we know the tail node of the reversed sub linked list, which is head.next
//we put the current node, which is head, behind the tail node.
head.next.next = head;
//don't forget to terminate the new tail
head.next = null;
return sub;
}
public static void main(String...args) {
MyNode head = createLinkedList();
MyNode preHead = new MyNode(head.value, head.next);
printResult(head);
head = reverse(head);
printResult(head);
printResult(preHead);
}
public static void printResult(MyNode head) {
System.out.println();
if(head == null) return;
while(head != null) {
System.out.print(head.value + " ");
head = head.next;
}
}
public static MyNode createLinkedList() {
MyNode head = new MyNode(1, null);
MyNode current = head;
for(int i = 2; i <= 4; i++) {
current.next = new MyNode(i, null);
current = current.next;
}
return head;
}
}
