/* reverse circular linked list 1 -> 2 -> 3 -> 4 -> 1 to 4 -> 3 -> 2 -> 1 -> 4
* notice there is no head node
*
* in place reverse
*
* step 1. store node 1 into a variable, head
* step 2. change node 2's next to node 1
* step 3. change node 3's next to node 2
* step 4. change node 4's next to node 3
* step 5. change node 1's next to node 4
* since node 1 is the same node as we stored variable head, we stops here
*
* The reverse method traversals the linked list once,
* the time complexity is O(N).
*
* This solution didn't create a new linked list, it changes the node's next value in place,
* the space complexity is O(1).
*
* */
public class CircularSolutionFour {
public static MyNode reverse(MyNode head) {
if(head == null || head.next == null) return head;
MyNode headStore = head;
MyNode pre = head;
MyNode current = head.next;
MyNode next = null;
while(current != headStore) {
//store next node before change the pointer
next = current.next;
//point the current node to previous node
current.next = pre;
//advance the previous node
pre = current;
//advance the current node
current = next;
}
//special treatment for the tail
current.next = pre;
return headStore;
}
public static void main(String...args) {
MyNode head = createLinkedList();
printResult(head);
head = reverse(head);
printResult(head);
}
public static void printResult(MyNode head) {
System.out.println();
if(head == null || head.next == null) return;
MyNode headMark = head;
while(head.next != headMark) {
System.out.print(head.value + " ");
head = head.next;
}
System.out.print(head.value + " ");
System.out.print(head.next.value + " ");
}
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;
}
current.next = head;
return head;
}
}
