今天刷到LeetCode第25題蓬坡，記錄一下刷題的思路猿棉，方便以后回看。（真的一周不寫就容易忘啊屑咳，所以還是要多練）
這個題大概有三種解法：
- 借助棧先進后出的思路萨赁，當鏈表元素k個一組放進棧中，然后在拿出來兆龙。（缺點是時間復雜度較高杖爽，入棧出棧都要遍歷鏈表，不推薦紫皇，了解思路即可）慰安。
- 遞歸：k個一組進行遞歸，具體思路請參考后面圖解聪铺。
- 迭代：同上化焕，參考后面圖解。
話不多說计寇，先上代碼：
借助棧
Deque<ListNode> stack = new LinkedList<>();
ListNode dummy = new ListNode(0);
//這個p會一直移動锣杂，需要另起一個指針
ListNode p = dummy;
while (true) {
int count = 0;
//這兒不能直接head移動，因為如果不足k個番宁，head指針將找不到元莫，因此另起一個指針
ListNode temp = head;
//k個一組放進棧中
while (temp != null && count < k) {
stack.push(temp);
temp = temp.next;
count++;
}
//當不足k個不用反轉
if (count != k) {
p.next = head;
break;
}
while (!stack.isEmpty()) {
p.next = stack.pop();
p = p.next;
}
//將head替換為k個位置之后，方便下次循環(huán)
head = temp;
}
return dummy.next;
這個思路其實沒啥好說的蝶押，用一個指針p依次的跟著棧往后移踱蠢，當不足k個時直接返回頭指針dummy.next。
看鏈表代碼的幾個重點思路
這里需要強調的幾點是在鏈表寫代碼時候的常識吧：
1、鏈表里面經(jīng)常會有如下代碼茎截，初學者看著會很奇怪苇侵，我一開始學習的時候也疑惑了很久：
ListNode dummy = new ListNode(0);
ListNode p = dummy;
這里已經(jīng)新創(chuàng)建了一個dummy，為啥還要再創(chuàng)建一個和dummy一樣的p企锌？為啥不直接用dummy?
原因是榆浓，當你新建的dummy節(jié)點在后續(xù)操作的時候，會進行移動撕攒，如p=p.next這種陡鹃，如果直接用dummy去操作，后面你拿到的dummy就不是原來的位置了抖坪，而是移動后的位置萍鲸，這時候如果你想要拿到原來的dummy，就需要新創(chuàng)建一個幫手去幫dummy做這個事擦俐，也就是p脊阴。
上面這個邏輯在鏈表代碼里面會經(jīng)常用到，搞懂其原因后在看代碼就不會有種云里霧里的感覺了蚯瞧。
2嘿期、鏈表里面經(jīng)常會出現(xiàn)下面這種xx.next滿天飛的情況，理解起來會很困難埋合。
head.next=next.next.next;
next.next=head;
你按照我的思路來想其實就會簡單很多秽五，當xx.next在表達式左邊的時候，就只有一個含義饥悴，xx的下一個節(jié)點指向表達式右邊的位置。
如head.next=next.next;就是指head指向next的下一個節(jié)點盲再。你這樣去梳理下以前看著比較懵逼的代碼就會清晰很多西设。反正我思路是清晰很多。
3答朋、一旦A.next=B之后贷揽，代表A以前指向的位置指針已經(jīng)斷開，現(xiàn)在指向B了梦碗。如果后續(xù)還需要用以前A.next的節(jié)點話就需要提前記錄下來禽绪。因此就會在鏈表了經(jīng)常出現(xiàn)下面這種代碼：
ListNode next = tail.next.next;
tail.next.next = prev.next;
prev.next = tail.next;
tail.next = next;
因為tail.next.next在第二行斷開了，第四行有需要用到洪规，所以會提前用Next把tail.next.next存起來印屁。
第三點乍看和第一點很像，但是還是有細微區(qū)別的斩例，一個是指針移動的記錄雄人，一個是指針斷開的記錄。
遞歸
int count = 0;
ListNode curr = head;
while (curr != null && count < k) {
curr = curr.next;
count++;
}
if (count == k) {
curr = reverseKGroup(curr, k);
while (count-- > 0) {
ListNode temp = head.next;
head.next = curr;
curr = head;
head = temp;
}
head = curr;
}
return head;
代碼其實還是很清晰的念赶，我們一點一點來理一下础钠。
int count = 0;
ListNode curr = head;
while (curr != null && count < k) {
curr = curr.next;
count++;
}
上面這段代碼的主要目的就是k個節(jié)點分組恰力，這里ListNode curr=head;要用我上面的基本點想一下，由于如果直接用head后移的話初始的head位置就找不到了旗吁，因此需要一個幫手curr去幫它做這個事踩萎。
接著往下看，如果有k個節(jié)點很钓，就k個一組翻轉香府，否則直接返回。
curr = reverseKGroup(curr, k); 這個是遞歸調用履怯，這里需要說明的一點是在看遞歸相關代碼不要強行去人肉遞歸回还，你會很痛苦的，且會把自己搞暈叹洲，畢竟我們不是機器柠硕。我們只需要知道這個代碼后面得出的結果就是經(jīng)過reverseKGroup(curr, k)這個函數(shù)處理的curr就直接是k個一組翻轉好的結果，我們現(xiàn)在唯一要做的就是运提，將curr前面的k個元素翻轉好在組裝就行蝗柔。
而下面的代碼就是做的這個事：
while (count-- > 0) {
ListNode temp = head.next;
head.next = curr;
curr = head;
head = temp;
}
head = curr;
這塊不是那么好理解，碰到這種情況一般畫個圖民泵，問題就迎刃而解了~
以head = [1,2,3,4,5], k = 3為例癣丧，圖畫的可能有點丑，但是可能會對你有點幫助栈妆。
這里k=3胁编，因此只會循環(huán)三次，當最后循環(huán)完curr的位置是在頭結點鳞尔，head的位置在temp嬉橙，因此后面需要將head=curr。最后返回head即可寥假。
迭代
int n = 0;
// 統(tǒng)計鏈表長度
for (ListNode i = head; i != null; n++, i = i.next);
ListNode dmy = new ListNode(0);
dmy.next = head;
for(ListNode prev = dmy, tail = head; n >= k; n -= k) {
for (int i = 1; i < k; i++) {
ListNode next = tail.next.next;
tail.next.next = prev.next;
prev.next = tail.next;
tail.next = next;
}
prev = tail;
tail = tail.next;
}
return dmy.next;
迭代的代碼可能會有點繞市框，xx.next.next這種樣式，不要有恐懼感糕韧，看懂之后思路還是很清晰的枫振。
前面兩行代碼是用n統(tǒng)計鏈表長度。其中遍歷鏈表的寫法還是很新穎的萤彩，值得借鑒粪滤。
下面在head前面構造了一個哨兵節(jié)點dummy，然后以dummy為prev,head為tail就開始翻轉了雀扶。
for(ListNode prev = dmy, tail = head; n >= k; n -= k)這塊代碼是將鏈表按k個一組開始進行翻轉额衙。
里面的for (int i = 1; i < k; i++)這里是從1開始而不是0開始，感覺會少循環(huán)一次。我是這么理解的窍侧，當有k個數(shù)县踢，其實真正翻轉的時候只會翻轉k-1次，這里1是沒問題的伟件。
具體的循環(huán)思路可以參考下圖硼啤，畫的有點亂，我相信你能看懂的~
一開始prev和tail是相鄰的斧账，tail.next.next=prev.next其實就是指將tail的下一個節(jié)點指向prev的下一個節(jié)點谴返，注意是tail的下一個節(jié)點不是tail。
然后prev.next=tail.next是指prev指向tail的下一個節(jié)點咧织。
tail.next=next是指tail指向原來tail.next.next位置嗓袱，這里不直接用tail.next.next是因為這個指針現(xiàn)在已經(jīng)斷掉了，所以用事先保存好的next习绢。
在k個一組翻轉完會將prev和tail進行重新賦值渠抹，在進行下一輪。
最后返回的是最開始的head節(jié)點位置闪萄，只是由于head現(xiàn)在已經(jīng)移動不知道到哪里去了梧却，所以用的是dummy.next，其實就是最開始的head位置败去。
寫在最后
這三個解法主要掌握遞歸和迭代即可放航，棧那個其實沒啥意義，時間復雜度太高圆裕，實際很難用到广鳍，除非什么特殊場景。
迭代和遞歸寫法其實都很繞吓妆，經(jīng)常會出現(xiàn)今天會寫搜锰，過一周看又有點不會了，所以多看多寫吧耿战，沒啥辦法，加油焊傅！
