/*
* Problem:
Reverse a linked list with K nodes as a group.
For example, given linked list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.
If K = 2, the reversed linked list is 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 7.
If K = 3, the reversed linked list is 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7.
If K = 4, the reversed linked list is 4 -> 3 -> 2 -> 1 -> 7 -> 6 -> 5.
Solution:
find the boundary of a sub-linkedlist, store head, tail, pre and next
reverse the sub-linkedlist
link pre to tail
advance head, tail, pre, next
*/
public class KReverseLinkedList {
private static int K = 3; //K >=1
private static int SIZE = 10; //SIZE >= 0
private class LNode {
int value;
LNode next;
LNode(int value, LNode next) {
this.value = value;
this.next = next;
}
}
private LNode makeLinkedList() {
LNode head = new LNode(0, null);
LNode current = head;
for(int i = 1; i <= SIZE; i++) {
current.next = new LNode(i, null);
current = current.next;
}
return head;
}
private void reverseLinkedList(LNode head, int k) {
if(k <= 1) {
return;
}
LNode pre = head;
LNode current = head.next;
LNode next = head;
//1->2->3->
//. / -
//3->2->1->
//- / .
for(int i = 1; i < k; i++) {
next = current.next;
current.next = pre; //point current node to previous node
pre = current;
current = next;
}
}
private void printLinkedList(LNode head) {
LNode current = head.next;
while(current != null) {
System.out.print(current.value + "->");
current = current.next;
}
System.out.println();
}
public static void main(String...args) {
KReverseLinkedList kr = new KReverseLinkedList();
LNode head0 = kr.makeLinkedList();
kr.printLinkedList(head0);
LNode head = head0.next;
LNode current = head;
//special treatment for head node
LNode pre = head0;
LNode next = current;
LNode tail = current;
//loop, keep reference of head ` and tail *
//3->2->1 4`->5->6*-> 7->8
//3->2->1-> 6*->5->4` 7->8
while(next != null) {
head = next;
int i = 0;
for(i = 1; i <= K; i++) { //for loop is to detect tail and sub linked list length
if(current == null) {
break;
}
tail = current;
current = current.next;
}
next = tail.next; //before reverse: 4`->5->6*
kr.reverseLinkedList(head, i - 1);
pre.next = tail; //after reverse 6*->5->4`
pre = head;
}
//special treatment for last node
pre.next = null;
kr.printLinkedList(head0);
}
}
