五月婷婷综合视频,一本色道久久综合无码人妻,亚洲无码视频在线观看观看,jizz日本美女,操小逼逼,日本韩国亚洲天堂网,刘玥一级婬片A片AAA,免费xx视频

前言

如果說數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ)，那么數(shù)組和鏈表就是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。因?yàn)橄穸?，棧，樹，圖等比較復(fù)雜的數(shù)組結(jié)基本上都可以由數(shù)組和鏈表來表示，所以掌握數(shù)組和鏈表的基本操作十分重要。

鏈表的知識(shí)點(diǎn)蠻多的，所以分成上下兩篇，這篇主要講解鏈表翻轉(zhuǎn)的解題技巧，下篇主要講關(guān)于鏈表快慢指針的知識(shí)點(diǎn)，干貨很多，建議先收藏再看。認(rèn)真看完保證收獲滿滿！

今天就來看看鏈表的基本操作及其在面試中的常見解題思路,本文將從以下幾個(gè)點(diǎn)來講解鏈表的核心知識(shí)

什么是鏈表，鏈表的優(yōu)缺點(diǎn)
鏈表的表示及基本操作
面試中鏈表的常見解題思路---翻轉(zhuǎn)

什么是鏈表

相信大家已經(jīng)開始迫不及待地想用鏈表解題了，不過在開始之前我們還是要先來溫習(xí)下鏈表的定義，以及它的優(yōu)勢與劣勢，磨刀不誤砍柴功！

鏈表的定義

鏈表是物理存儲(chǔ)單元上非連續(xù)的、非順序的存儲(chǔ)結(jié)構(gòu)，它是由一個(gè)個(gè)結(jié)點(diǎn)，通過指針來聯(lián)系起來的，其中每個(gè)結(jié)點(diǎn)包括數(shù)據(jù)和指針。

鏈表的非連續(xù)，非順序，對應(yīng)數(shù)組的連續(xù)，順序，我們來看看整型數(shù)組 1，2，3，4 在內(nèi)存中是如何表示的

可以看到數(shù)組的每個(gè)元素都是連續(xù)緊鄰分配的，這叫連續(xù)性，同時(shí)由于數(shù)組的元素占用的大小是一樣的，在 Java 中 int 型大小固定為 4 個(gè)字節(jié),所以如果數(shù)組的起始地址是 100，由于這些元素在內(nèi)存中都是連續(xù)緊鄰分配的，大小也一樣，可以很容易地找出數(shù)組中任意一個(gè)元素的位置，比如數(shù)組中的第三個(gè)元素起始地址為 100 + 2 * 4 = 108,這就叫順序性。查找的時(shí)間復(fù)雜度是O(1),效率很高！

那鏈表在內(nèi)存中是怎么表示的呢

可以看到每個(gè)結(jié)點(diǎn)都分配在非連續(xù)的位置，結(jié)點(diǎn)與結(jié)點(diǎn)之間通過指針連在了一起，所以如果我們要找比如值為 3 ?的結(jié)點(diǎn)時(shí)，只能通過結(jié)點(diǎn) 1 從頭到尾遍歷尋找，如果元素少還好，如果元素太多（比如超過一萬個(gè)），每個(gè)元素的查找都要從頭開始查找，時(shí)間復(fù)雜度是O(n)，比起數(shù)組的 O(1)，差距不小。

除了查找性能鏈表不如數(shù)組外，還有一個(gè)優(yōu)勢讓數(shù)組的性能高于鏈表,這里引入程序局部性原理，啥叫程序局部性原理。

我們知道 CPU 運(yùn)行速度是非?？斓?，如果 CPU 每次運(yùn)算都要到內(nèi)存里去取數(shù)據(jù)無疑是很耗時(shí)的，所以在 CPU 與內(nèi)存之間往往集成了挺多層級(jí)的緩存，這些緩存越接近CPU，速度越快，所以如果能提前把內(nèi)存中的數(shù)據(jù)加載到如下圖中的 L1, L2, L3 緩存中，那么下一次 CPU 取數(shù)的話直接從這些緩存里取即可，能讓CPU執(zhí)行速度加快，那什么情況下內(nèi)存中的數(shù)據(jù)會(huì)被提前加載到 L1,L2,L3 緩存中呢，答案是當(dāng)某個(gè)元素被用到的時(shí)候，那么這個(gè)元素地址附近的的元素會(huì)被提前加載到緩存中

以上文整型數(shù)組 1，2，3，4為例，當(dāng)程序用到了數(shù)組中的第一個(gè)元素（即 1）時(shí)，由于 CPU 認(rèn)為既然 1 被用到了，那么緊鄰它的元素 2，3，4 被用到的概率會(huì)很大，所以會(huì)提前把 2，3，4 加到 L1,L2,L3 緩存中去，這樣 CPU 再次執(zhí)行的時(shí)候如果用到 2，3，4，直接從 L1,L2,L3 緩存里取就行了，能提升不少性能

畫外音：如果把 CPU 的一個(gè)時(shí)種看成一秒，則從 L1 讀取數(shù)據(jù)需要 3 秒，從 L2 讀取需要 11 秒，L3讀取需要 25秒，而從內(nèi)存讀取呢，需要 1 分 40 秒，所以程序局部性原理能對 CPU 執(zhí)行性能有很大的提升

而鏈表呢，由于鏈表的每個(gè)結(jié)點(diǎn)在內(nèi)存里都是隨機(jī)分布的，只是通過指針聯(lián)系在一起，所以這些結(jié)點(diǎn)的地址并不相鄰，自然無法利用 程序局部性原理 來提前加載到 L1,L2,L3 緩存中來提升程序性能。

畫外音：程序局部性原理是計(jì)算機(jī)中非常重要的原理，這里不做展開，建議大家查閱相關(guān)資料詳細(xì)了解一下

如上所述，相比數(shù)組，鏈表的非連續(xù)，非順序確實(shí)讓它在性能上處于劣勢，那什么情況下該使用鏈表呢？考慮以下情況

大內(nèi)存空間分配

由于數(shù)組空間的連續(xù)性，如果要為數(shù)組分配 500M 的空間，這 500M 的空間必須是連續(xù)的，未使用的，所以在內(nèi)存空間的分配上數(shù)組的要求會(huì)比較嚴(yán)格，如果內(nèi)存碎片太多，分配連續(xù)的大空間很可能導(dǎo)致失敗。而鏈表由于是非連續(xù)的，所以這種情況下選擇鏈表更合適。

元素頻繁刪除和插入

如果涉及到元素的頻繁刪除和插入，用鏈表就會(huì)高效很多，對于數(shù)組來說，如果要在元素間插入一個(gè)元素，需要把其余元素一個(gè)個(gè)往后移（如圖示），以為新元素騰空間（同理，如果是刪除則需要把被刪除元素之后的元素一個(gè)個(gè)往前移），效率上無疑是比較低的。

(在 1，2 間插入 5，需要把2，3，4 同時(shí)往后移一位)

而鏈表的插入刪除相對來說就比較簡單了，修改指針位置即可，其他元素?zé)o需做任何移動(dòng)操作（如圖示：以插入為例）

綜上所述：如果數(shù)據(jù)以查為主，很少涉及到增和刪，選擇數(shù)組，如果數(shù)據(jù)涉及到頻繁的插入和刪除，或元素所需分配空間過大，傾向于選擇鏈表。

說了這么多理論，相信讀者對數(shù)組和鏈表的區(qū)別應(yīng)該有了更深刻地認(rèn)識(shí)了，尤其是 程序局部性原理，是不是開了不少眼界^_^，如果面試中問到數(shù)組和鏈表的區(qū)別能回答到程序局部性原理，會(huì)是一個(gè)非常大的亮點(diǎn)！

接下來我們來看看鏈表的表現(xiàn)形式和解題技巧

需要說明的是有些代碼像打印鏈表等限于篇幅的關(guān)系沒有在文中展示，我把文中所有相關(guān)代碼都放到 github 中了，大家如果需要，可以訪問我的 github 地址: https://github.com/allentofight/algorithm 下載運(yùn)行（微信不支持外鏈，建議大家 copy 之后瀏覽器打開再下載運(yùn)行），文中所有代碼均已用 Java 實(shí)現(xiàn)并運(yùn)行通過

鏈表的表示

由于鏈表的特點(diǎn)（查詢或刪除元素都要從頭結(jié)點(diǎn)開始）,所以我們只要在鏈表中定義頭結(jié)點(diǎn)即可,另外如果要頻繁用到鏈表的長度，還可以額外定義一個(gè)變量來表示。

需要注意的是這個(gè)頭結(jié)點(diǎn)的定義是有講究的，一般來說頭結(jié)點(diǎn)有兩種定義形式，一種是直接以某個(gè)元素結(jié)點(diǎn)為頭結(jié)點(diǎn),如下

一種是以一個(gè)虛擬的節(jié)點(diǎn)作為頭結(jié)點(diǎn)，即我們常說的哨兵，如下

定義這個(gè)哨兵有啥好處呢，假設(shè)我們不定義這個(gè)哨兵，來看看鏈表及添加元素的基本操作怎么定義的

/**
* 鏈表中的結(jié)點(diǎn)，data代表節(jié)點(diǎn)的值，next是指向下一個(gè)節(jié)點(diǎn)的引用
 */
class Node {
int data;// 結(jié)點(diǎn)的數(shù)組域，值
    Node next = null;// 節(jié)點(diǎn)的引用，指向下一個(gè)節(jié)點(diǎn)
public Node(int data) {
this.data = data;
    }
}

/**
* 鏈表
 */
public class LinkedList {
int length = 0; // 鏈表長度，非必須，可不加
    Node head = null; // 頭結(jié)點(diǎn)

public void addNode(int val) {
if (head == null) {
            head = new Node(val);
        } else {
            Node tmp = head;
while (tmp.next != null) {
                tmp.next = tmp;
            }
            tmp.next = new Node(val);
        }
    }
}

發(fā)現(xiàn)問題了嗎，注意看下面代碼

有兩個(gè)問題：

每插入一個(gè)元素都要對頭結(jié)點(diǎn)進(jìn)行判空比較，如果一個(gè)鏈表有很多元素需要插入，就需要進(jìn)行很多次的判空處理，不是那么高效
頭結(jié)點(diǎn)與其他結(jié)點(diǎn)插入邏輯不統(tǒng)一（一個(gè)需要判空后再插入，一個(gè)不需要判空直接插入）,從程序邏輯性來說不是那么合理（因?yàn)榻Y(jié)點(diǎn)與結(jié)點(diǎn)是平級(jí)，添加邏輯理應(yīng)相同）

如果定義了哨兵結(jié)點(diǎn)，以上兩個(gè)問題都可解決，來看下使用哨兵結(jié)點(diǎn)的鏈表定義

public class LinkedList {
int length = 0; // 鏈表長度，非必須，可不加
    Node head = new Node(0); // 哨兵結(jié)點(diǎn)
public void addNode(int val) {
        Node tmp = head;
while (tmp.next != null) {
            tmp.next = tmp;
        }
        tmp.next = new Node(val);
    }
}

可以看到，定義了哨兵結(jié)點(diǎn)的鏈表邏輯上清楚了很多,不用每次插入元素都對頭結(jié)點(diǎn)進(jìn)行判空，也統(tǒng)一了每一個(gè)結(jié)點(diǎn)的添加邏輯。

所以之后的習(xí)題講解中我們使用的鏈表都是使用定義了哨兵結(jié)點(diǎn)的形式。

做了這么多前期的準(zhǔn)備工作，終于要開始我們的正餐了：鏈表解題常用套路--翻轉(zhuǎn)！

鏈表常見解題套路

熱身賽

既然我們要用鏈表解題，那我們首先就構(gòu)造一個(gè)鏈表吧?

題目：給定數(shù)組 1，2，3，4 構(gòu)造如下鏈表 head-->4---->3---->2---->1

看清楚了，是逆序構(gòu)造鏈表！順序構(gòu)造我們都知道怎么構(gòu)造，對每個(gè)元素持續(xù)調(diào)用上文代碼定義的 addNode 方法即可（即尾插法），與尾插法對應(yīng)的，是頭插法，即把每一個(gè)元素插到頭節(jié)點(diǎn)后面即可，這樣就能做到逆序構(gòu)造鏈表，如圖示（以插入1，2 為例）

頭插法比較簡單，直接上代碼,直接按以上動(dòng)圖的步驟來完成邏輯，如下

public class LinkedList {
int length = 0; // 鏈表長度，非必須，可不加
    Node head = new Node(0); // 哨兵節(jié)點(diǎn)

// 頭插法
public void headInsert(int val) {
// 1.構(gòu)造新結(jié)點(diǎn)
        Node newNode = new Node(val);
// 2.新結(jié)點(diǎn)指向頭結(jié)點(diǎn)之后的結(jié)點(diǎn)
        newNode.next = head.next;
// 3.頭結(jié)點(diǎn)指向新結(jié)點(diǎn)
        head.next = newNode;
    }

public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
int[] arr = {1,2,3,4};
// 頭插法構(gòu)造鏈表
for (int i = 0; i < arr.length; i++) {
            linkedList.headInsert(arr[i]);
        }
// 打印鏈表,將打印 4-->3-->2-->1
        linkedList.printList();
    }
}

小試牛刀

現(xiàn)在我們加大一下難度，來看下曾經(jīng)的 Google 面試題：給定單向鏈表的頭指針和一個(gè)節(jié)點(diǎn)指針，定義一個(gè)函數(shù)在 O(1) 內(nèi)刪除這個(gè)節(jié)點(diǎn)。

如圖示：給定值為 2 的結(jié)點(diǎn)，如何把這個(gè)結(jié)點(diǎn)給刪了。

我們知道，如果給定一個(gè)結(jié)點(diǎn)要?jiǎng)h除它的后繼結(jié)點(diǎn)是很簡單的，只要把這個(gè)結(jié)點(diǎn)的指針指向后繼結(jié)點(diǎn)的后繼結(jié)點(diǎn)即可

如圖示：給定結(jié)點(diǎn) 2，刪除它的后繼結(jié)點(diǎn) 3，把結(jié)點(diǎn) 2 的 next 指針指向 3 的后繼結(jié)點(diǎn) 4 即可。

但給定結(jié)點(diǎn) 2，該怎么刪除結(jié)點(diǎn) 2 本身呢，注意題目沒有規(guī)定說不能改變結(jié)點(diǎn)中的值，所以有一種很巧妙的方法，貍貓換太子！我們先通過結(jié)點(diǎn) 2 找到結(jié)點(diǎn) 3，再把節(jié)點(diǎn) 3 的值賦給結(jié)點(diǎn) 2，此時(shí)結(jié)點(diǎn) 2 的值變成了 3，這時(shí)候問題就轉(zhuǎn)化成了上圖這種比較簡單的需求，即根據(jù)結(jié)點(diǎn) 2 把結(jié)點(diǎn) 3 移除即可，看圖

不過需要注意的是這種解題技巧只適用于被刪除的指定結(jié)點(diǎn)是中間結(jié)點(diǎn)的情況，如果指定結(jié)點(diǎn)是尾結(jié)點(diǎn)，還是要老老實(shí)實(shí)地找到尾結(jié)點(diǎn)的前繼結(jié)點(diǎn)，再把尾結(jié)點(diǎn)刪除，代碼如下

/**
 * 刪除指定的結(jié)點(diǎn)
 * @param deletedNode
 */
public void removeSelectedNode(Node deletedNode) {
// 如果此結(jié)點(diǎn)是尾結(jié)點(diǎn)我們還是要從頭遍歷到尾結(jié)點(diǎn)的前繼結(jié)點(diǎn)，再將尾結(jié)點(diǎn)刪除
if (deletedNode.next == null) {
        Node tmp = head;
while (tmp.next != deletedNode) {
            tmp = tmp.next;
        }
// 找到尾結(jié)點(diǎn)的前繼結(jié)點(diǎn)，把尾結(jié)點(diǎn)刪除
        tmp.next = null;
    } else {
        Node nextNode = deletedNode.next;
// 將刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)的值賦給被刪除結(jié)點(diǎn)
        deletedNode.data = nextNode.data;
// 將 nextNode 結(jié)點(diǎn)刪除
        deletedNode.next = nextNode.next;
        nextNode.next = null;
    }
}

入門到進(jìn)階:鏈表翻轉(zhuǎn)

接下來我們會(huì)重點(diǎn)看一下鏈表的翻轉(zhuǎn)，鏈表的翻轉(zhuǎn)可以衍生出很多的變形，是面試中非常熱門的考點(diǎn)，基本上考鏈表必考翻轉(zhuǎn)！所以掌握鏈表的翻轉(zhuǎn)是必修課！

什么是鏈表的翻轉(zhuǎn):給定鏈表 head-->4--->3-->2-->1，將其翻轉(zhuǎn)成 head-->1-->2-->3-->4 ，由于翻轉(zhuǎn)鏈表是如此常見，如此重要，所以我們分別詳細(xì)講解下如何用遞歸和非遞歸這兩種方式來解題

遞歸翻轉(zhuǎn)

關(guān)于遞歸的文章之前寫了三篇總結(jié)了遞歸的常見解題套路,給出了遞歸解題的常見四步曲，如果看完對以下遞歸的解題套路會(huì)更加深刻，這里不做贅述了，我們直接套遞歸的解題思路：

首先我們要查看翻轉(zhuǎn)鏈表是否符合遞歸規(guī)律：問題可以分解成具有相同解決思路的子問題，子子問題...，直到最終的子問題再也無法分解。

要翻轉(zhuǎn) head--->4--->3-->2-->1 鏈表，不考慮 head 結(jié)點(diǎn)，分析 4--->3-->2-->1，仔細(xì)觀察我們發(fā)現(xiàn)只要先把 3-->2-->1 翻轉(zhuǎn)成 3<----2<----1，之后再把 3 指向 4 即可（如下圖示）

圖：翻轉(zhuǎn)鏈表主要三步驟

只要按以上步驟定義好這個(gè)翻轉(zhuǎn)函數(shù)的功能即可，這樣由于子問題與最初的問題具有相同的解決思路，拆分后的子問題持續(xù)調(diào)用這個(gè)翻轉(zhuǎn)函數(shù)即可達(dá)到目的。

注意看上面的步驟1，問題的規(guī)模是不是縮小了（如下圖），從翻轉(zhuǎn)整個(gè)鏈表變成了只翻轉(zhuǎn)部分鏈表！問題與子問題都是從某個(gè)結(jié)點(diǎn)開始翻轉(zhuǎn)，具有相同的解決思路，另外當(dāng)縮小到只翻轉(zhuǎn)一個(gè)結(jié)點(diǎn)時(shí)，顯然是終止條件，符合遞歸的條件！之后的翻轉(zhuǎn) 3-->2-->1, 2-->1 持續(xù)調(diào)用這個(gè)定義好的遞歸函數(shù)即可！

既然符合遞歸的條件，那我們就可以用遞歸規(guī)則來解題（注意翻轉(zhuǎn)之后 head 的后繼節(jié)點(diǎn)變了，需要重新設(shè)置！別忘了這一步）

1、定義遞歸函數(shù),明確函數(shù)的功能根據(jù)以上分析，這個(gè)遞歸函數(shù)的功能顯然是翻轉(zhuǎn)某個(gè)節(jié)點(diǎn)開始的鏈表，然后返回新的頭結(jié)點(diǎn)

/**
 * 翻轉(zhuǎn)結(jié)點(diǎn) node 開始的鏈表
 */
public Node invertLinkedList(Node node) {
}

2、尋找遞推公式上文中已經(jīng)詳細(xì)畫出了翻轉(zhuǎn)鏈表的步驟，簡單總結(jié)一下遞推步驟如下

針對結(jié)點(diǎn) node (值為 4), 先翻轉(zhuǎn) node 之后的結(jié)點(diǎn) ? invert(node->next) ,翻轉(zhuǎn)之后 4--->3--->2--->1 變成了 4--->3<---2<---1
再把 node 節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)（3）指向 node，node 的后繼節(jié)點(diǎn)設(shè)置為空（避免形成環(huán)），此時(shí)變成了 4<---3<---2<---1
返回新的頭結(jié)點(diǎn)，因?yàn)榇藭r(shí)新的頭節(jié)點(diǎn)從原來的 4 變成了 1，需要重新設(shè)置一下 head

3、將遞推公式代入第一步定義好的函數(shù)中，如下 (invertLinkedList)

/**
 * 遞歸翻轉(zhuǎn)結(jié)點(diǎn) node 開始的鏈表
 */
public Node invertLinkedList(Node node) {
if (node.next == null) {
return node;
    }

// 步驟 1: 先翻轉(zhuǎn) node 之后的鏈表
    Node newHead = invertLinkedList(node.next);

// 步驟 2: 再把原 node 節(jié)點(diǎn)后繼結(jié)點(diǎn)的后繼結(jié)點(diǎn)指向 node，node 的后繼節(jié)點(diǎn)設(shè)置為空(防止形成環(huán))
    node.next.next = node;
    node.next = null;

// 步驟 3: 返回翻轉(zhuǎn)后的頭結(jié)點(diǎn)
return newHead;
}

public static void main(String[] args) {
    LinkedList linkedList = new LinkedList();
int[] arr = {4,3,2,1};
for (int i = 0; i < arr.length; i++) {
        linkedList.addNode(arr[i]);
    }
    Node newHead = linkedList.invertLinkedList(linkedList.head.next);
// 翻轉(zhuǎn)后別忘了設(shè)置頭結(jié)點(diǎn)的后繼結(jié)點(diǎn)！
    linkedList.head.next = newHead;
    linkedList.printList();      // 打印 1，2，3，4
}

畫外音：翻轉(zhuǎn)后由于 head 的后繼結(jié)點(diǎn)變了，別忘了重新設(shè)置哦！

4、計(jì)算時(shí)間/空間復(fù)雜度由于遞歸調(diào)用了 n 次 invertLinkedList 函數(shù)，所以時(shí)間復(fù)雜度顯然是 O(n), 空間復(fù)雜度呢，沒有用到額外的空間，但是由于遞歸調(diào)用了 ?n 次 invertLinkedList 函數(shù)，壓了 n 次棧，所以空間復(fù)雜度也是 O(n)。

遞歸一定要從函數(shù)的功能去理解，從函數(shù)的功能看，定義的遞歸函數(shù)清晰易懂，定義好了之后，由于問題與被拆分的子問題具有相同的解決思路，所以子問題只要持續(xù)調(diào)用定義好的功能函數(shù)即可，切勿層層展開子問題，此乃遞歸常見的陷阱！仔細(xì)看函數(shù)的功能，其實(shí)就是按照下圖實(shí)現(xiàn)的。(對照著代碼看，是不是清晰易懂^_^)

非遞歸翻轉(zhuǎn)鏈表（迭代解法）

我們知道遞歸比較容易造成棧溢出，所以如果有其他時(shí)間/空間復(fù)雜度相近或更好的算法，應(yīng)該優(yōu)先選擇非遞歸的解法,那我們看看如何用迭代來翻轉(zhuǎn)鏈表，主要思路如下

步驟 1：定義兩個(gè)節(jié)點(diǎn)：pre, cur ，其中 cur 是 pre 的后繼結(jié)點(diǎn)，如果是首次定義，需要把 pre 指向 cur 的指針去掉，否則由于之后鏈表翻轉(zhuǎn)，cur 會(huì)指向 pre，就進(jìn)行了一個(gè)環(huán)(如下)，這一點(diǎn)需要注意

步驟2：知道了 cur 和 pre,翻轉(zhuǎn)就容易了，把 cur 指向 pre 即可，之后把 cur 設(shè)置為 pre ，cur 的后繼結(jié)點(diǎn)設(shè)置為 cur 一直往前重復(fù)此步驟即可,完整動(dòng)圖如下

注意：同遞歸翻轉(zhuǎn)一樣，迭代翻轉(zhuǎn)完了之后 head 的后繼結(jié)點(diǎn)從 4 變成了 1，記得重新設(shè)置一下。

知道了解題思路，實(shí)現(xiàn)代碼就容易多了，直接上代碼

/**
 * 迭代翻轉(zhuǎn)
 */
public void iterationInvertLinkedList() {
// 步驟 1
    Node pre = head;
    Node cur = pre.getNext();
    pre.setNext(null);   // pre 是頭結(jié)點(diǎn)，避免翻轉(zhuǎn)鏈表后形成環(huán)

// 步驟 2
while (cur != null) {
/**
         * 務(wù)必注意!!!：在 cur 指向 pre 之前一定要先保留 cur 的后繼結(jié)點(diǎn)，不然如果 cur 先指向 pre，之后就再也找不到后繼結(jié)點(diǎn)了
         */
        Node next = cur.getNext();
        cur.setNext(pre);
        pre = cur;
        cur = next;
    }
// 此時(shí) pre 指向的是原鏈表的尾結(jié)點(diǎn)，翻轉(zhuǎn)后即為鏈表 head 的后繼結(jié)點(diǎn)
    head.next = pre;
}

用迭代的思路來做由于循環(huán)了 n 次，顯然時(shí)間復(fù)雜度為 O(n),另外由于沒有額外的空間使用，也未像遞歸那樣調(diào)用遞歸函數(shù)不斷壓棧，所以空間復(fù)雜度是 O(1),對比遞歸，顯然應(yīng)該使用迭代的方式來處理！

花了這么大的精力我們總算把翻轉(zhuǎn)鏈表給搞懂了，如果大家看了之后幾道翻轉(zhuǎn)鏈表的變形，會(huì)發(fā)現(xiàn)我們花了這么大篇幅講解翻轉(zhuǎn)鏈表是值得的。

接下來我們來看看鏈表翻轉(zhuǎn)的變形

變形題 1：給定一個(gè)鏈表的頭結(jié)點(diǎn) head,以及兩個(gè)整數(shù) from 和 to ,在鏈表上把第 from 個(gè)節(jié)點(diǎn)和第 to 個(gè)節(jié)點(diǎn)這一部分進(jìn)行翻轉(zhuǎn)。例如：給定如下鏈表，from = 2, to = 4 head-->5-->4-->3-->2-->1 將其翻轉(zhuǎn)后，鏈表變成 head-->5--->2-->3-->4-->1

有了之前翻轉(zhuǎn)整個(gè)鏈表的解題思路，現(xiàn)在要翻轉(zhuǎn)部分鏈表就相對簡單多了,主要步驟如下:

根據(jù) from 和 to 找到 from-1, from, to, ?to+1 四個(gè)結(jié)點(diǎn)(注意臨界條件，如果 from 從頭結(jié)點(diǎn)開始，則 from-1 結(jié)點(diǎn)為空, 翻轉(zhuǎn)后需要把 to 設(shè)置為頭結(jié)點(diǎn)的后繼結(jié)點(diǎn)， from 和 to 結(jié)點(diǎn)也可能超過尾結(jié)點(diǎn),這兩種情況不符合條件不翻轉(zhuǎn))。
對 from 到 to 的結(jié)點(diǎn)進(jìn)行翻轉(zhuǎn)
將 from-1 節(jié)點(diǎn)指向 to 結(jié)點(diǎn)，將 from 結(jié)點(diǎn)指向 to + 1 結(jié)點(diǎn)

知道了以上的思路，代碼就簡單了,按上面的步驟1，2，3 實(shí)現(xiàn)，注釋也寫得很詳細(xì)，看以下代碼（對 from 到 to 結(jié)點(diǎn)的翻轉(zhuǎn)我們使用迭代翻轉(zhuǎn)，當(dāng)然使用遞歸也是可以的，限于篇幅關(guān)系不展開，大家可以嘗試一下）。

/**
 * 迭代翻轉(zhuǎn) from 到 to 的結(jié)點(diǎn)
 */
public void iterationInvertLinkedList(int fromIndex, int toIndex) throws Exception {

    Node fromPre = null;            // from-1結(jié)點(diǎn)
    Node from = null;               // from 結(jié)點(diǎn)
    Node to = null;                 // to 結(jié)點(diǎn)
    Node toNext = null;             // to+1 結(jié)點(diǎn)

// 步驟 1：找到  from-1, from, to,  to+1 這四個(gè)結(jié)點(diǎn)
    Node tmp = head.next;
int curIndex = 1;      // 頭結(jié)點(diǎn)的index為1
while (tmp != null) {
if (curIndex == fromIndex-1) {
            fromPre = tmp;
        } else if (curIndex == fromIndex) {
            from = tmp;
        } else if (curIndex == toIndex) {
            to = tmp;
        } else if (curIndex == toIndex+1) {
            toNext = tmp;
        }
        tmp = tmp.next;
        curIndex++;
    }

if (from == null || to == null) {
// from 或 to 都超過尾結(jié)點(diǎn)不翻轉(zhuǎn)
throw new Exception("不符合條件");
    }

// 步驟2：以下使用循環(huán)迭代法翻轉(zhuǎn)從 from 到 to 的結(jié)點(diǎn)
    Node pre = from;
    Node cur = pre.next;
while (cur != toNext) {
        Node next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }

// 步驟3：將 from-1 節(jié)點(diǎn)指向 to 結(jié)點(diǎn)（如果從 head 的后繼結(jié)點(diǎn)開始翻轉(zhuǎn)，則需要重新設(shè)置 head 的后繼結(jié)點(diǎn)），將 from 結(jié)點(diǎn)指向 to + 1 結(jié)點(diǎn)
if (fromPre != null) {
        fromPre.next = to;
    } else {
        head.next = to;
    }
    from.next = toNext;
}

變形題 2：給出一個(gè)鏈表，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)，并返回翻轉(zhuǎn)后的鏈表。k 是一個(gè)正整數(shù)，它的值小于或等于鏈表的長度。如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么將最后剩余節(jié)點(diǎn)保持原有順序。

示例 : 給定這個(gè)鏈表：head-->1->2->3->4->5 當(dāng) k = 2 時(shí)，應(yīng)當(dāng)返回: head-->2->1->4->3->5 當(dāng) k = 3 時(shí)，應(yīng)當(dāng)返回: head-->3->2->1->4->5 說明 :

你的算法只能使用常數(shù)的額外空間。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

這道題是 LeetCode 的原題,屬于 hard 級(jí)別，如果這一題你懂了，那對鏈表的翻轉(zhuǎn)應(yīng)該基本沒問題了，有了之前的翻轉(zhuǎn)鏈表基礎(chǔ)，相信這題不難。

只要我們能找到翻一組 k 個(gè)結(jié)點(diǎn)的方法，問題就解決了（之后只要重復(fù)對 k 個(gè)結(jié)點(diǎn)一組的鏈表進(jìn)行翻轉(zhuǎn)即可）。

接下來，我們以以下鏈表為例來看看怎么翻轉(zhuǎn) 3 個(gè)一組的鏈表（此例中 k = 3）

首先，我們要記錄 3 個(gè)一組這一段鏈表的前繼結(jié)點(diǎn),定義為 startKPre,然后再定義一個(gè) step, 從這一段的頭結(jié)點(diǎn) (1）開始遍歷 2 次，找出這段鏈表的起始和終止結(jié)點(diǎn)，如下圖示
找到 startK 和 endK 之后，根據(jù)之前的迭代翻轉(zhuǎn)法對 startK 和 endK 的這段鏈表進(jìn)行翻轉(zhuǎn)
然后將 startKPre 指向 endK,將 startK 指向 endKNext，即完成了對 k 個(gè)一組結(jié)點(diǎn)的翻轉(zhuǎn)。

知道了一組 k 個(gè)怎么翻轉(zhuǎn)，之后只要重復(fù)對 k 個(gè)結(jié)點(diǎn)一組的鏈表進(jìn)行翻轉(zhuǎn)即可，對照圖示看如下代碼應(yīng)該還是比較容易理解的

/**
 * 每 k 個(gè)一組翻轉(zhuǎn)鏈表
 * @param k
 */
public void iterationInvertLinkedListEveryK(int k) {
    Node tmp = head.next;
int step = 0;               // 計(jì)數(shù)，用來找出首結(jié)點(diǎn)和尾結(jié)點(diǎn)

    Node startK = null;         // k個(gè)一組鏈表中的頭結(jié)點(diǎn)
    Node startKPre = head;      // k個(gè)一組鏈表頭結(jié)點(diǎn)的前置結(jié)點(diǎn)
    Node endK;                  // k個(gè)一組鏈表中的尾結(jié)點(diǎn)
while (tmp != null) {
// tmp 的下一個(gè)節(jié)點(diǎn),因?yàn)橛捎诜D(zhuǎn)，tmp 的后繼結(jié)點(diǎn)會(huì)變,要提前保存
        Node tmpNext = tmp.next;
if (step == 0) {
// k 個(gè)一組鏈表區(qū)間的頭結(jié)點(diǎn)
            startK = tmp;
            step++;
        } else if (step == k-1) {
// 此時(shí)找到了 k 個(gè)一組鏈表區(qū)間的尾結(jié)點(diǎn)（endK）,對這段鏈表用迭代進(jìn)行翻轉(zhuǎn)
            endK = tmp;
            Node pre = startK;
            Node cur = startK.next;
if (cur == null) {
break;
            }
            Node endKNext = endK.next;
while (cur != endKNext) {
                Node next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
// 翻轉(zhuǎn)后此時(shí) endK 和 startK 分別是是 k 個(gè)一組鏈表中的首尾結(jié)點(diǎn)
            startKPre.next = endK;
            startK.next = endKNext;

// 當(dāng)前的 k 個(gè)一組翻轉(zhuǎn)完了，開始下一個(gè) k 個(gè)一組的翻轉(zhuǎn)
            startKPre = startK;
            step = 0;
        } else {
            step++;
        }
        tmp = tmpNext;
    }
}

時(shí)間復(fù)雜度是多少呢，對鏈表從頭到尾循環(huán)了 n 次，同時(shí)每 k 個(gè)結(jié)點(diǎn)翻轉(zhuǎn)一次，可以認(rèn)為總共翻轉(zhuǎn)了 n 次，所以時(shí)間復(fù)雜度是O(2n),去掉常數(shù)項(xiàng)，即為 O(n)。注：這題時(shí)間復(fù)雜度比較誤認(rèn)為是O(k * n),實(shí)際上并不是每一次鏈表的循環(huán)都會(huì)翻轉(zhuǎn)鏈表，只是在循環(huán)鏈表元素每 k 個(gè)結(jié)點(diǎn)的時(shí)候才會(huì)翻轉(zhuǎn)

變形題 3: 變形 2 針對的是順序的 k 個(gè)一組翻轉(zhuǎn)，那如何逆序 k 個(gè)一組進(jìn)行翻轉(zhuǎn)呢

例如：給定如下鏈表， head-->1-->2-->3-->4-->5 逆序 k 個(gè)一組翻轉(zhuǎn)后，鏈表變成

head-->1--->3-->2-->5-->4?（k = 2 時(shí)）?

這道題是字節(jié)跳動(dòng)的面試題，確實(shí)夠變態(tài)的，順序 k 個(gè)一組翻轉(zhuǎn)都已經(jīng)屬于 hard 級(jí)別了，逆序 k 個(gè)一組翻轉(zhuǎn)更是屬于 super hard 級(jí)別了，不過其實(shí)有了之前知識(shí)的鋪墊，應(yīng)該不難，只是稍微變形了一下，只要對鏈表做如下變形即可

代碼的每一步其實(shí)都是用了我們之前實(shí)現(xiàn)好的函數(shù)，所以我們之前做的每一步都是有伏筆的哦！就是為了解決字節(jié)跳動(dòng)這道終極面試題！

/**
 * 逆序每 k 個(gè)一組翻轉(zhuǎn)鏈表
 * @param k
 */
public void reverseIterationInvertLinkedListEveryK(int k) {
// 先翻轉(zhuǎn)鏈表
    iterationInvertLinkedList();
// k 個(gè)一組翻轉(zhuǎn)鏈表
    iterationInvertLinkedListEveryK(k);
// 再次翻轉(zhuǎn)鏈表
    iterationInvertLinkedList();
}

由此可見，掌握基本的鏈表翻轉(zhuǎn)非常重要！難題多是在此基礎(chǔ)了做了相應(yīng)的變形而已

總結(jié)

本文詳細(xì)講解了鏈表與數(shù)組的本質(zhì)區(qū)別，相信大家對兩者的區(qū)別應(yīng)該有了比較深刻的認(rèn)識(shí)，尤其是程序局部性原理，相信大家看了應(yīng)該會(huì)眼前一亮，之后通過對鏈表的翻轉(zhuǎn)由淺入深地介紹，相信之后的鏈表翻轉(zhuǎn)對大家應(yīng)該不是什么難事了，不過建議大家親自實(shí)現(xiàn)一遍文中的代碼哦，這樣印象會(huì)更深刻一些！有時(shí)候看起來思路是這么一回事，但真正操作起來還是會(huì)有不少坑，紙上得來終覺淺，絕知此事要躬行！

我畫了20張圖,終于讓女朋友都學(xué)會(huì)了翻轉(zhuǎn)鏈表

前言