題目
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
解題思路：
用一個指針p遍歷鏈表，另一個指針q指向p的下一個節(jié)點伸但，然后用q往后遍歷，并用cnt計數(shù)，如果后面有p后面沒有k個元素則推出循環(huán)聊训，如果p后面有k個元素卵史，就用q將p后面的k-1節(jié)點取出來碱工，放到p的前面，當(dāng)插入第一個k-1個節(jié)點時狸相，將q放到head之前就行，可以用head來操作捐川，之后的話脓鹃，就必須用一個prev節(jié)點來定位q要插入的位置，開始prev指向p的前面的指針古沥，q就插入到p的前面瘸右，prev的后面娇跟，之后，q就插入到prev的后面太颤。
代碼：
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null)
return null;
if (k == 1)
return head;
ListNode last = new ListNode(0);
last.next = head;
head=last;
while (last.next != null) {
ListNode p1 = last.next;
int count = 1;
while (count < k && p1.next != null) {
p1 = p1.next;
count++;
}
if (count == k) {
p1 = last.next;
ListNode p0 = p1;
ListNode p2 = p1.next;
while (count-- > 1) {
ListNode tmp = p2.next;
p2.next = p1;
p1 = p2;
p2 = tmp;
}
last.next = p1;
p0.next = p2;
last = p0;
} else {
break;
}
}
return head.next;
}
參考鏈接：
http://www.shangxueba.com/jingyan/1819445.html
http://blog.csdn.net/tingmei/article/details/8050556
