圖解：如何旋轉(zhuǎn)鏈表
前言
題目：
示例 1：
解釋：
向右旋轉(zhuǎn) 1 步：5->1->2->3->4->NULL
向右旋轉(zhuǎn) 2 步：4->5->1->2->3->NULL
示例 2：
輸入：0->1->2->NULL, k = 4
輸出：2->0->1->NULL
解釋：
向右旋轉(zhuǎn) 1 步：2->0->1->NULL
向右旋轉(zhuǎn) 2 步：1->2->0->NULL
向右旋轉(zhuǎn) 3 步：0->1->2->NULL
向右旋轉(zhuǎn) 4 步：2->0->1->NULL?
畫外音：Leetcode第61題，中等/難度，通過率40.6%? ?。?！
先分段后連接
下圖為鏈表分別向右旋轉(zhuǎn)2、3、4個(gè)位置后的情況。
經(jīng)過觀察，我們不難發(fā)現(xiàn)：
k=2時(shí), 鏈表從位置3節(jié)點(diǎn)后分成兩部分；
k=3時(shí),?鏈表從位置2節(jié)點(diǎn)后分成兩部分；
k=4時(shí),?鏈表從位置1節(jié)點(diǎn)后分成兩部分。
然后尾節(jié)點(diǎn)指向頭節(jié)點(diǎn)就可以實(shí)現(xiàn)鏈表的旋轉(zhuǎn)。
那么，這道看似旋轉(zhuǎn)的題就很簡(jiǎn)單了，我們可以將其分為三步：
找到分段節(jié)點(diǎn)位置；
從分段節(jié)點(diǎn)后斷開；
將尾節(jié)點(diǎn)指向頭節(jié)點(diǎn)。
頭節(jié)點(diǎn)位置是已知的，分段節(jié)點(diǎn)位置(位置3/位置2等)如何獲取呢？
根據(jù)初始狀態(tài)圖：
位置3節(jié)點(diǎn)指向倒數(shù)第k=2個(gè)節(jié)點(diǎn)；
位置2節(jié)點(diǎn)指向倒數(shù)第k=3個(gè)節(jié)點(diǎn)；
位置1節(jié)點(diǎn)指向倒數(shù)第k=4個(gè)節(jié)點(diǎn)。
《圖解：刪除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn)》里提到的前后雙指針方法在這里就可以派上用場(chǎng)了。
畫外音：為了與Leetcode保持一致，在這里沒有使用單鏈表基礎(chǔ)知識(shí)里實(shí)現(xiàn)的鏈表結(jié)構(gòu)(主要區(qū)別在哨兵節(jié)點(diǎn))。
可能有人發(fā)現(xiàn)了，這里的k值都是小于鏈表長(zhǎng)度的。那么當(dāng)k大于等于鏈表長(zhǎng)度時(shí)，如何定位分段節(jié)點(diǎn)位置呢？
由上圖可以看出：
當(dāng)k為鏈表長(zhǎng)度的倍數(shù)時(shí)，鏈表是維持原狀的。當(dāng)k為非倍數(shù)時(shí)，分段節(jié)點(diǎn)位置為len-(k%len)，指向倒數(shù)第k%len個(gè)節(jié)點(diǎn)。
那么問題就迎刃而解了?。?！
代碼實(shí)現(xiàn)：
struct?ListNode*?rotateRight(struct?ListNode*?head,?int?k){
????if?(head?==?NULL?||?head->next?==?NULL?||?k?==?0)?{
????????return?head;
????}
????struct?ListNode*?p,*q,*newHead,*tmp?=?head;
????int?len,i;
????len?=?i?=?0;
????//?求出鏈表長(zhǎng)度
????while?(tmp?!=?NULL)?{
????????tmp?=?tmp->next;
????????len++;
????}
????k?=?k?%?len;
????//?k為鏈表長(zhǎng)度倍數(shù)時(shí)旋轉(zhuǎn)后還是原位置
????if?(k?==?0)?{
????????return?head;
????}
????p?=?q?=?(struct?ListNode*)malloc(sizeof(struct?ListNode));
????p->next?=?head;
????q->next?=?head;
????while(i?????????q?=?q?->?next;
????????i++;
????}
????while?(q->next?!=?NULL)?{
????????q?=?q?->?next;
????????p?=?p?->?next;
????}
????newHead?=?p->next;
????p->next?=?NULL;
????q->next?=?head;
????return?newHead;
}先連接后分段
既然最終會(huì)將頭節(jié)點(diǎn)指向尾節(jié)點(diǎn)，我們能不能一開始就把鏈表首尾相連，找到分段位置，將其斷開呢？
那么我們的操作順序就變?yōu)榱耍?/span>
鏈表首尾相連；
找到分段位置；
從分段節(jié)點(diǎn)后斷開。
代碼實(shí)現(xiàn)：
struct?ListNode*?rotateRight(struct?ListNode*?head,?int?k){
????if?(head?==?NULL?||?head->next?==?NULL)?{
????????return?head;
????}
????struct?ListNode?*q,*p?=?head;
????int?len?=?1;
????//?求出鏈表長(zhǎng)度
????while?(p->next?!=?NULL)?{
????????p?=?p->next;
????????len++;
????}
????p->next?=?head;???//?鏈表首尾相連成環(huán)
????p?=?head;
????k?=?len?-?(k?%?len);
????while?(k?>?0?&&?p?!=?NULL)?{
????????q?=?p;????????? //?新尾節(jié)點(diǎn)
????????p?=?p->next;????//?新頭結(jié)點(diǎn)
????????k--;
????}
????q->next?=?NULL;
????return?p;
}其實(shí)，這種方式與上邊的方法在本質(zhì)上是沒有區(qū)別的，只是將首尾相連的操作前置了。不過可以作為一種解題思路。
總結(jié)
1、本文中介紹了兩種旋轉(zhuǎn)鏈表的方式：
先分段后連接：將鏈表先從分段節(jié)點(diǎn)后分割開，然后首尾連接起來；
先連接后分段：將鏈表先首尾連接起來，再?gòu)姆侄喂?jié)點(diǎn)后分割開。
2、分段節(jié)點(diǎn)位置計(jì)算方式為len-(k % len)，所指向節(jié)點(diǎn)位置計(jì)算方式為k%len。
文章整體目錄
如何獲取
很簡(jiǎn)單，在我的微信公眾號(hào)?帥地玩編程?回復(fù)?程序員內(nèi)功修煉?即可獲取《程序員內(nèi)功修煉》第一版和第二版的 PDF。
推薦，推薦一個(gè) GitHub，這個(gè) GitHub 整理了幾百本常用技術(shù)PDF，絕大部分核心的技術(shù)書籍都可以在這里找到，GitHub地址：https://github.com/iamshuaidi/CS-Book（電腦打開體驗(yàn)更好），地址閱讀原文直達(dá)