package StackMin.ReverseList_offer16;
public class ReverseKgroup_extend_offer16 {
/**
* 分组反转单链表，最后不足K个节点的部分也反转
*
* @param head
* @param k
* @return
*/
public static ListNode reverseKgroup(ListNode head, int k) {
if (head == null)
return head;
ListNode cur = head;
ListNode reHead = null;
int count = 0;
/* Reverse first k nodes of linked list */
while (count < k && cur != null) {
ListNode reCur = cur;
cur = cur.next;
reCur.next = reHead;
reHead = reCur;
count++;
}
/*
* cur is now a pointer to (k+1)th node Recursively call for the
* list starting from current. And make rest of the list as next of
* first node
*/
if (cur != null)
head.next = reverseKgroup(cur, k);
return reHead;
}
}package StackMin.ReverseList_offer16;
public class ReverseKgroup_extend_offer16 {
/**
* 分组反转单链表，最后不足K个节点的部分也反转
*
* @param head
* @param k
* @return
*/
/*
输入的原始单链表为3-5-6-9-7-2-1-12，其中K为3；
经过第一次while循环，单链表变为6-5-3-9-7-2-1-12。此时跳出while循环是因为count<k不成立了，cur节点指向了9，head节点指向了3。
所以接着判断cur是否为null，若不是，则刚好递归求出head.next。
经过第二次while循环，单链表为6-5-3-2-7-9-1-12。此时跳出while循环是因为count<k不成立了，cur节点指向了1，head节点指向了9。
接着判断cur，并且递归求head.next节点。
第三次循环，跳出while是因为cur==null了，直接返回reHead，此时reHead指向了12。
*/
public ListNode reverseKgroup(ListNode head, int k) {
if (head == null)
return head;
ListNode cur = head;
ListNode reHead = null;
int count = 0;
/* Reverse first k nodes of linked list */
while (count < k && cur != null) {
ListNode reCur = cur;
cur = cur.next;
reCur.next = reHead;
reHead = reCur;
count++;
}
/*
* cur is now a pointer to (k+1)th node Recursively call for the
* list starting from current. And make rest of the list as next of
* first node
*/
if (cur != null)
head.next = reverseKgroup(cur, k);
return reHead;
}
public static void main(String[] args) {
ListNode head = new ListNode(3);
ListNode L2 = new ListNode(5);
ListNode L3 = new ListNode(6);
ListNode L4 = new ListNode(9);
ListNode L5 = new ListNode(7);
ListNode L6 = new ListNode(2);
ListNode L7 = new ListNode(1);
ListNode L8 = new ListNode(12);
head.next = L2;
L2.next = L3;
L3.next = L4;
L4.next = L5;
L5.next = L6;
L6.next = L7;
L7.next = L8;
ReverseKgroup_extend_offer16 reverseKgroup_extend_offer16 = new ReverseKgroup_extend_offer16();
reverseKgroup_extend_offer16.printListNode(head);
System.out.println();
ListNode node = reverseKgroup_extend_offer16.reverseKgroup(head, 3);
reverseKgroup_extend_offer16.printListNode(node);
}
public void printListNode(ListNode node) {
while (node != null) {
if (node.next == null) {
System.out.print(node.val);
} else {
System.out.print(node.val + ">");
}
node = node.next;
}
}
}package StackMin.ReverseList_offer16;
public class ListNode {
int val;
public ListNode next = null;
ListNode(int val) {
this.val = val;
}
}