搞懂單鏈表常見面試題

Hello 繼上次的搞懂基本排序算法蕊唐，這個(gè)一星期作谚，我總結(jié)了迫悠，我所學(xué)習(xí)和思考的單鏈表基礎(chǔ)知識(shí)和常見面試題携添，這些題有的來自《劍指 offer》 ,有的來自《程序員代碼面試指南》，有的來自 leetCode叛本，不是很全面沪蓬，但都具有一定代表性，相信大家看完以后一定跟我一樣来候，對(duì)面試的時(shí)候算法題又多了一份自信跷叉。

什么是單鏈表

鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表营搅，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)云挟，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)，簡單來說鏈表并不像數(shù)組那樣將數(shù)組存儲(chǔ)在一個(gè)連續(xù)的內(nèi)存地址空間里转质，它們可以不是連續(xù)的因?yàn)樗麄兠總€(gè)節(jié)點(diǎn)保存著下一個(gè)節(jié)點(diǎn)的引用（地址）园欣，所以較之?dāng)?shù)組來說這是一個(gè)優(yōu)勢(shì)。

對(duì)于單鏈表的一個(gè)節(jié)點(diǎn)我們經(jīng)常使用下邊這種代碼表示：

public class Node{
    //節(jié)點(diǎn)的值
    int value休蟹；
    //指向下一個(gè)節(jié)點(diǎn)的指針（java 中表現(xiàn)為下一個(gè)節(jié)點(diǎn)的引用）
    Node next沸枯；
    
    public void Node(int value){
        this.value = value;
    }
}

單鏈表的特點(diǎn)

鏈表增刪元素的時(shí)間復(fù)雜度為O(1),查找一個(gè)元素的時(shí)間復(fù)雜度為 O(n);
單鏈表不用像數(shù)組那樣預(yù)先分配存儲(chǔ)空間的大小，避免了空間浪費(fèi)
單鏈表不能進(jìn)行回溯操作赂弓，如：只知道鏈表的頭節(jié)點(diǎn)的時(shí)候無法快讀快速鏈表的倒數(shù)第幾個(gè)節(jié)點(diǎn)的值绑榴。

單鏈表的基本操作

上一節(jié)我們說了什么是單鏈表，那么我們都知道一個(gè)數(shù)組它具有增刪改查的基本操作拣展，那么我們單鏈表作為一種常見的數(shù)據(jù)結(jié)構(gòu)類型也是具有這些操作的那么我們就來看下對(duì)于單鏈表有哪些基本操作：

獲取單鏈表的長度

由于單鏈表的存儲(chǔ)地址不是連續(xù)的彭沼，鏈表并不具有直接獲取鏈表長度的功能，對(duì)于一個(gè)鏈表的長度我們只能一次去遍歷鏈表的節(jié)點(diǎn)备埃，直到找到某個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為空的時(shí)候得到鏈表的總長度姓惑，注意這里的出發(fā)點(diǎn)并不是一個(gè)空鏈表然后依次添加節(jié)點(diǎn)后，然后去讀取已經(jīng)記錄的節(jié)點(diǎn)個(gè)數(shù)按脚，而是已知一個(gè)鏈表的頭結(jié)點(diǎn)然后去獲取這個(gè)鏈表的長度：

public int getLength(Node head){
    
    if(head == null){
        return 0;
    }
    
    int len = 0;
    while(head != null){
        len++;
        head = head.next;
    }  
    return len;  
}

查詢指定索引的節(jié)點(diǎn)值或指定值得節(jié)點(diǎn)值的索引

由于鏈表是一種非連續(xù)性的存儲(chǔ)結(jié)構(gòu)于毙，節(jié)點(diǎn)的內(nèi)存地址不是連續(xù)的，也就是說鏈表不能像數(shù)組那樣可以通過索引值獲取索引位置的元素辅搬。所以鏈表的查詢的時(shí)間復(fù)雜度要是O(n)級(jí)別的唯沮，這點(diǎn)和數(shù)組查詢指定值得元素位置是相同的脖旱，因?yàn)槟阋檎业臇|西在內(nèi)存中的存儲(chǔ)地址都是不一定的。

    /** 獲取指定角標(biāo)的節(jié)點(diǎn)值 */
    public int getValueOfIndex(Node head, int index) throws Exception {

        if (index < 0 || index >= getLength(head)) {
            throw new Exception("角標(biāo)越界介蛉！");
        }

        if (head == null) {
            throw new Exception("當(dāng)前鏈表為空萌庆！");
        }

        Node dummyHead = head;

        while (dummyHead.next != null && index > 0) {
            dummyHead = dummyHead.next;
            index--;
        }

        return dummyHead.value;
    }

    
    /** 獲取節(jié)點(diǎn)值等于 value 的第一個(gè)元素角標(biāo) */
    public int getNodeIndex(Node head, int value) {
    
            int index = -1;
            Node dummyHead = head;
    
            while (dummyHead != null) {
                index++;
                if (dummyHead.value == value) {
                    return index;
                }
                dummyHead = dummyHead.next;
            }
    
            return -1;
    }

鏈表添加一個(gè)元素

學(xué)過數(shù)據(jù)結(jié)構(gòu)的朋友一定知道鏈表的插入操作，分為頭插法币旧，尾插法践险，隨機(jī)節(jié)點(diǎn)插入法，當(dāng)然數(shù)據(jù)結(jié)構(gòu)講得時(shí)候也是針對(duì)一個(gè)已經(jīng)構(gòu)造好的（保存了鏈表頭部節(jié)點(diǎn)和尾部節(jié)點(diǎn)引用）的情況下去插入一個(gè)元素吹菱，這看上去很簡單巍虫，如果我們?cè)谥恢酪粋€(gè)鏈表的頭節(jié)點(diǎn)的情況下去插入一個(gè)元素，就不是那么簡單了鳍刷，就對(duì)于頭插入法我們只需要構(gòu)造一個(gè)新的節(jié)點(diǎn)占遥，然后將這個(gè)節(jié)點(diǎn)的 next 指針指向已知鏈表的頭節(jié)點(diǎn)就可以了。

1输瓜、在已有鏈表頭部插入一個(gè)節(jié)點(diǎn)

public Node addAtHead(Node head, int value){
     Node newHead = new Node(value);
     newHead.next = head;
     return newHead;
}

2瓦胎、在已有鏈表的尾部插入一個(gè)節(jié)點(diǎn)：

public void addAtTail(Node head, int value){
     Node node = new Node(value);
     Node dummyHead = head;
     
     //找到未節(jié)點(diǎn) 注意這里是當(dāng)元素的下一個(gè)元素為空的時(shí)候這個(gè)節(jié)點(diǎn)即為未節(jié)點(diǎn)
     while( dummyHead.next != null){
        dummyHead = dummyHead.next;
     }
     
     dummyHead.next = node;   
}

3、在指定位置添加一個(gè)節(jié)點(diǎn)

// 注意這里 index 從 0 開始
 public Node insertElement(Node head, int value, int index) throws Exception {
   //為了方便這里我們假設(shè)知道鏈表的長度
   int length = getLength(head);
   if (index < 0 || index >= length) {
       throw new Exception("角標(biāo)越界尤揣！");
   }

   if (index == 0) {
       return addAtHead(head, value);
   } else if (index == length - 1) {
       addAtTail(head, value);
   } else {

       Node pre = head;
       Node cur = head.next;
       //
       while (pre != null && index > 1) {
           pre = pre.next;
           cur = cur.next;
           index--;
       }

       //循環(huán)結(jié)束后 pre 保存的是索引的上一個(gè)節(jié)點(diǎn) 而 cur 保存的是索引值當(dāng)前的節(jié)點(diǎn)
       Node node = new Node(value);
       pre.next = node;
       node.next = cur;
   }
   return head;
}

在指定位置添加一個(gè)節(jié)點(diǎn)凛捏，首先我們應(yīng)該找到這個(gè)索引所在的節(jié)點(diǎn)的前一個(gè)，以及該節(jié)點(diǎn)芹缔，分別記錄這兩個(gè)節(jié)點(diǎn)，然后將索引所在節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的 next 指針指向新節(jié)點(diǎn)瓶盛，然后將新節(jié)點(diǎn)的 next 指針指向插入節(jié)點(diǎn)即可最欠。與其他元素并沒有什么關(guān)系，所以單鏈表插入一個(gè)節(jié)點(diǎn)時(shí)間復(fù)雜度為 O(1)惩猫，而數(shù)組插入元素就不一樣了如果將一個(gè)元素插入數(shù)組的指定索引位置芝硬，那么該索引位置以后元素的索引位置(內(nèi)存地址)都將發(fā)生變化，所以一個(gè)數(shù)組的插入一個(gè)元素的時(shí)間復(fù)雜度為 O(n);所以鏈表相對(duì)于數(shù)組插入的效率要高一些轧房，刪除同理拌阴。

鏈表刪除一個(gè)元素

由于上邊介紹了鏈表添加元素的方法這里對(duì)于鏈表刪除節(jié)點(diǎn)的方法不在詳細(xì)介紹直接給出代碼：

1、刪除頭部節(jié)點(diǎn) 也就是刪除索引為 0 的節(jié)點(diǎn)：

    public Node deleteHead(Node head) throws Exception {
        if (head == null) {
            throw new Exception("當(dāng)前鏈表為空奶镶！");
        }
        return head.next;
    }

2迟赃、刪除尾節(jié)點(diǎn)

    public void deleteTail(Node head) throws Exception {

        if (head == null) {
            throw new Exception("當(dāng)前鏈表為空！");
        }

        Node dummyHead = head;
        while (dummyHead.next != null && dummyHead.next.next != null) {
            dummyHead = dummyHead.next;
        }
        dummyHead.next = null;
    }

3厂镇、刪除指定索引的節(jié)點(diǎn)：

public Node deleteElement(Node head, int index) throws Exception {

   int size = getLength(head);
   
   if (index < 0 || index >= size) {
       throw new Exception("角標(biāo)越界纤壁！");
   }

   if (index == 0) {
       return deleteHead(head);
   } else if (index == size - 1) {
       deleteTail(head);
   } else {
       Node pre = head;

       while (pre.next != null && index > 1) {
           pre = pre.next;
           index--;
       }

       //循環(huán)結(jié)束后 pre 保存的是索引的上一個(gè)節(jié)點(diǎn) 將其指向索引的下一個(gè)元素
       if (pre.next != null) {
           pre.next = pre.next.next;
       }
   }

   return head;
}

由單鏈表的增加刪除可以看出，鏈表的想要對(duì)指定索引進(jìn)行操作（增加捺信，刪除）酌媒，的時(shí)候必須獲取該索引的前一個(gè)元素。記住這句話，對(duì)鏈表算法題很有用秒咨。

單鏈表常見面試題

介紹了鏈表的常見操作以后喇辽，我們的目標(biāo)是學(xué)習(xí)鏈表常見的面試題目，不然我們學(xué)他干嘛呢雨席，哈哈~ 開個(gè)玩笑那么我們就先從簡單的面試題開始：

尋找單鏈表的中間元素

同學(xué)們可能看到這道面試題笑了菩咨，咋這么簡單，拿起筆來就開始寫舅世，遍歷整個(gè)鏈表旦委，拿到鏈表的長度len，再次遍歷鏈表那么位于 len/2 位置的元素就是鏈表的中間元素雏亚。

咱也不能說這種方法不對(duì)哲虾，想想一下一個(gè)騰訊的面試官坐在對(duì)面問這個(gè)問題，這個(gè)回答顯然連自己這一關(guān)都很難過去峡懈。那么更漸快的方法是什么呢媳禁？或者說時(shí)間復(fù)雜度更小的方法如何實(shí)現(xiàn)這次查找？這里引出一個(gè)很關(guān)鍵的概念就是 快慢指針法网持，這也是面試官想考察的宜岛。

假如我們?cè)O(shè)置兩個(gè)指針 slow、fast 起始都指向單鏈表的頭節(jié)點(diǎn)功舀。其中 fast 的移動(dòng)速度是 slow 的2倍萍倡。當(dāng) fast 指向末尾節(jié)點(diǎn)的時(shí)候，slow 正好就在中間了辟汰。想想一下是不是這樣假設(shè)一個(gè)鏈表長度為 6 列敲， slow 每次一個(gè)節(jié)點(diǎn)位置， fast 每次移動(dòng)兩個(gè)節(jié)點(diǎn)位置帖汞，那么當(dāng)fast = 5的時(shí)候 slow = 2 正好移動(dòng)到 2 的節(jié)點(diǎn)的位置戴而。

所以求解鏈表中間元素的解題思路是：

    public Node getMid(Node head){
      if(head == null){
         return null;
      }
      
      Node slow = head;
      Node fast = head;
      
      // fast.next = null 表示 fast 是鏈表的尾節(jié)點(diǎn)
      while(fast != null && fast.next != null){
         fast = fast.next.next;
         slow = slow.next;
      }
      return slow;
    }

判斷一個(gè)鏈表是否是循環(huán)鏈表

首先此題也是也是考察快慢指針的一個(gè)題，也是快慢指針的第二個(gè)應(yīng)用翩蘸。先簡單說一下什么循環(huán)鏈表所意，循環(huán)鏈表其實(shí)就是單鏈表的尾部指針指向頭指針，構(gòu)建成一個(gè)環(huán)形的鏈表催首，叫做循環(huán)鏈表扶踊。如 1 -> 2 - > 3 -> 1 -> 2 .....。為什么快慢指針再循環(huán)鏈表中總能相遇呢翅帜？你可以想象兩個(gè)人在賽跑姻檀，A的速度快，B的速度慢涝滴，經(jīng)過一定時(shí)間后绣版，A總是會(huì)和B相遇胶台，且相遇時(shí)A跑過的總距離減去B跑過的總距離一定是圈長的n倍。這也就是 Floyd判環(huán)(圈)算法杂抽。

那么如何使用快慢指針去判斷一個(gè)鏈表是否為環(huán)形鏈表呢：


private static boolean isLoopList(Node head){

        if (head == null){
            return false;
        }

        
        Node slow = head;
        Node fast = head.next;
        
        //如果不是循環(huán)鏈表那么一定有尾部節(jié)點(diǎn) 此節(jié)點(diǎn) node.next = null
        while(slow != null && fast != null && fast.next != null){
            if (fast == slow || fast.next == slow){
                return true;
            }
            // fast 每次走兩步  slow 每次走一步
            fast =fast.next.next;
            slow = slow.next;
        }
        //如果不是循環(huán)鏈表返回 false
        return false;
    }

已知一個(gè)單鏈表求倒數(shù)第 N 個(gè)節(jié)點(diǎn)

為什么這個(gè)題要放在快慢指針的后邊呢诈唬，因?yàn)檫@個(gè)題的解題思想和快慢指針相似，我們可以想一下：如果我們讓快指針先走 n-1 步后缩麸，然后讓慢指針出發(fā)铸磅。快慢指針每次都只移動(dòng)一個(gè)位置杭朱，當(dāng)快指針移動(dòng)到鏈表末尾的時(shí)候阅仔，慢指針是否就正處于倒數(shù)第 N 個(gè)節(jié)點(diǎn)的位置呢。

是這里把這兩個(gè)指針稱之為快慢指針是不正確的弧械，因?yàn)榭炻羔樖侵敢粋€(gè)指針移動(dòng)的快一個(gè)指針移動(dòng)的慢八酒，而此題中快指針只是比慢指針先移動(dòng)了 n-1 個(gè)位置而已，移動(dòng)速度是相同的刃唐。

如果上邊的講解不好理解羞迷，這里提供另外一種思路，就是想象一下画饥，上述快慢指針的移動(dòng)過程衔瓮，是否就相當(dāng)于一個(gè)固定窗口大小為 n 的滑動(dòng)窗口：

n = 1 fast 指針不移動(dòng) fast 到達(dá)最后一個(gè)節(jié)點(diǎn) 即 fast.next 的時(shí)候 slow 也到達(dá)尾部節(jié)點(diǎn)滿條件
n = len fast 指針移動(dòng) n-1（len -1 ）次 fast 到達(dá)最后一個(gè)節(jié)點(diǎn) slow 位于頭節(jié)點(diǎn)不變滿足條件兩個(gè)臨界值均滿足我們這種假設(shè)。
1< n < len 的時(shí)候我們假設(shè) n = 2 抖甘，那么 fast 比 slow 先移動(dòng)一步,也就是窗口大小為 2热鞍，那么當(dāng) fast.next = null 即 fast 已經(jīng)指向鏈表最后一個(gè)節(jié)點(diǎn)的時(shí)候，slow 就指向了倒數(shù)第二個(gè)節(jié)點(diǎn)衔彻。

下面我們來看下函數(shù)實(shí)現(xiàn)：

     /**
     * 注意我們一般說倒數(shù)第 n 個(gè)元素 n 是從 1 開始的
     */
    private Node getLastIndexNode(Node head, int n) {

        // 輸入的鏈表不能為空碍现，并且 n 大于0
        if (n < 1 || head == null) {
            return null;
        }

        n = 10;
        // 指向頭結(jié)點(diǎn)
        Node fast = head;
        // 倒數(shù)第k個(gè)結(jié)點(diǎn)與倒數(shù)第一個(gè)結(jié)點(diǎn)相隔 n-1 個(gè)位置
        // fast 先走 n-1 個(gè)位置
        for (int i = 1; i < n; i++) {
            // 說明還有結(jié)點(diǎn)
            if (fast.next != null) {
                fast = fast.next;
            }else {
                // 已經(jīng)沒有節(jié)點(diǎn)了，但是i還沒有到達(dá)k-1說明k太大米奸，鏈表中沒有那么多的元素
                return null;
            }
        }

        Node slow = head;
        // fast 還沒有走到鏈表的末尾，那么 fast 和 slow 一起走爽篷，
        // 當(dāng) fast 走到最后一個(gè)結(jié)點(diǎn)即悴晰，fast.next=null 時(shí)，slow 就是倒數(shù)第 n 個(gè)結(jié)點(diǎn)
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 返回結(jié)果
        return slow;
}

刪除單鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)

看到這個(gè)題時(shí)候樂了逐工，這考察的知識(shí)點(diǎn)不就是一道求解倒數(shù)第 n 個(gè)節(jié)點(diǎn)的進(jìn)化版么铡溪。但是我們也說過，如果想操作鏈表的某個(gè)節(jié)點(diǎn)(添加泪喊，刪除)還必須知道這個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)棕硫。所以我們刪除倒數(shù)第 n 個(gè)元素就要找到倒數(shù)第 n + 1 個(gè)元素。然后將倒數(shù)第 n + 1個(gè)元素 p 的 next 指針 p.next 指向 p.next.next 袒啼。

我們找到倒數(shù)第 n 個(gè)節(jié)點(diǎn)的時(shí)候哈扮，先讓 fast 先走了 n-1 步纬纪，那么我們刪除倒數(shù)第 n 個(gè)節(jié)點(diǎn)的時(shí)候就需要讓 fast 先走 n 步，構(gòu)建一個(gè) n+1 大小的窗口滑肉，然后 fast 和 slow 整體平移到鏈表尾部包各，slow 指向的節(jié)點(diǎn)就是倒數(shù)第 n+1 個(gè)節(jié)點(diǎn)。

這里我們還可以使用滑動(dòng)窗口的思想來考慮臨界值：

n = 1 的時(shí)候我們需要構(gòu)建的窗口為 2,也就是當(dāng) fast.next = null 的時(shí)候 slow 在的倒數(shù)第二個(gè)節(jié)點(diǎn)上靶庙，那么可想而知是滿足我們的條件的问畅。
當(dāng) 1 < n < len 的時(shí)候我們總是能構(gòu)建出這樣的一個(gè) len + 1大小的窗口，n 最大為 len -1 的時(shí)候六荒，slow 位于頭節(jié)點(diǎn)护姆，fast 位于未節(jié)點(diǎn)，刪除倒數(shù)第 n 個(gè)元素掏击，即刪除正數(shù)第二個(gè)節(jié)點(diǎn)卵皂，slow.next = slow.next.next 即可。
當(dāng) n > len 的時(shí)候可想而知铐料，我們要找的倒數(shù)第 n 個(gè)元素不存在渐裂，此時(shí)返回頭節(jié)點(diǎn)就好了
n = len 的時(shí)候比較特殊，循環(huán)并沒有因?yàn)榈箶?shù)第 len 個(gè)元素不存在而終止钠惩，并進(jìn)行了 fast = fast.next; 循環(huán)結(jié)束后 fast 指向 null , 且此時(shí) slow 位于頭節(jié)點(diǎn)柒凉，所以我們要?jiǎng)h除的節(jié)點(diǎn)是頭節(jié)點(diǎn)，只需要在循環(huán)結(jié)束后判斷如果 fast == null 返回 head.next 即可

下面我們來看解法：

/**
 * 刪除倒是第 n 個(gè)節(jié)點(diǎn) 我們就要找到倒數(shù)第 n + 1 個(gè)節(jié)點(diǎn)篓跛， 如果 n > len 則返回原列表
 */
private Node deleteLastNNode(Node head, int n) {

   if (head == null || n < 1) {
       return head;
   }

   Node fast = head;
   
   //注意 我們要構(gòu)建長度為 n + 1 的窗口 所以 i 從 0 開始
   for (int i = 0; i < n; i++) {
       //fast 指針指向倒數(shù)第一個(gè)節(jié)點(diǎn)的時(shí)候膝捞，就是要?jiǎng)h除頭節(jié)點(diǎn)
       if (fast == null) {
           return head;
       } else {
           fast = fast.next;
       }
   }

   // 由于 n = len 再循環(huán)內(nèi)部沒有判斷直接前進(jìn)了一個(gè)節(jié)點(diǎn)，臨界值 n = len 的時(shí)候 循環(huán)完成或 fast = null
   if (fast == null){
       return head.next;
   }

   //此時(shí) n 一定是小于 len 的 且 fast 先走了 n 步
   Node pre = head;

   while (fast.next != null) {
       fast = fast.next;
       pre = pre.next;
   }

   pre.next = pre.next.next;

   return head;
}

旋轉(zhuǎn)單鏈表

題目：給定一個(gè)鏈表愧沟，旋轉(zhuǎn)鏈表蔬咬，使得每個(gè)節(jié)點(diǎn)向右移動(dòng)k個(gè)位置，其中k是一個(gè)非負(fù)數(shù)沐寺。
如給出鏈表為 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

做完林艘，刪除倒數(shù)第 n 個(gè)節(jié)點(diǎn)的題，我們?cè)诳粗李}是不是很簡單了混坞，這道題的本質(zhì)就是狐援，找到 k 位置節(jié)點(diǎn) 將其變成尾節(jié)點(diǎn)，然后原來鏈表的尾節(jié)點(diǎn)指向原來的頭節(jié)點(diǎn)

private Node rotateList(Node head, int n) {

   int start = 1;

   Node fast = head;

   //先讓快指針走 n 給個(gè)位置
   while (start < n && fast.next != null) {
       fast = fast.next;
       start++;
   }


   //循環(huán)結(jié)束后如果 start < n 表示 n 整個(gè)鏈表還要長 旋轉(zhuǎn)后還是原鏈表
   //如果 fast.next = null 表示 n 正好等于原鏈表的長度此時(shí)也不需要旋轉(zhuǎn)
   if (fast.next == null || start < n) {
       return head;
   }

   //倒數(shù)第 n + 1個(gè)節(jié)點(diǎn)
   Node pre = fast;
   //旋轉(zhuǎn)后的頭節(jié)點(diǎn)
   Node newHead = fast.next;

   while (fast.next != null) {
       fast = fast.next;
   }
   //原鏈表的最后一個(gè)節(jié)點(diǎn)指向原來的頭節(jié)點(diǎn)
   fast.next = head;
   //將旋轉(zhuǎn)的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)變?yōu)槲补?jié)點(diǎn)
   pre.next = null;

   return newHead;
}

翻轉(zhuǎn)單鏈表

翻轉(zhuǎn)一個(gè)單鏈表究孕，要求額外的空間復(fù)雜度為 O(1)

翻轉(zhuǎn)單鏈表是我感覺比較難的基礎(chǔ)題啥酱，那么先來屢一下思路：一個(gè)節(jié)點(diǎn)包含指向下一節(jié)點(diǎn)的引用，翻轉(zhuǎn)的意思就是對(duì)要原來指向下一個(gè)節(jié)點(diǎn)引用指向上一個(gè)節(jié)點(diǎn)

找到當(dāng)前要反轉(zhuǎn)的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)并用變量保存因?yàn)橄乱淮我崔D(zhuǎn)的是它
然后讓當(dāng)前節(jié)點(diǎn)的 next 指向上一個(gè)節(jié)點(diǎn)厨诸，上一個(gè)節(jié)點(diǎn)初始 null 因?yàn)轭^結(jié)點(diǎn)的翻轉(zhuǎn)后變?yōu)槲补?jié)點(diǎn)
當(dāng)前要反轉(zhuǎn)的節(jié)點(diǎn)變成了下一個(gè)要比較元素的上一個(gè)節(jié)點(diǎn)镶殷，用變量保存
當(dāng)前要比較的節(jié)點(diǎn)賦值為之前保存的未翻轉(zhuǎn)前的下一個(gè)節(jié)點(diǎn)
當(dāng)前反轉(zhuǎn)的節(jié)點(diǎn)為 null 的時(shí)候，保存的上一個(gè)節(jié)點(diǎn)即翻轉(zhuǎn)后的鏈表頭結(jié)點(diǎn)

ok微酬，不知道按照上邊我寫的步驟能否理解一個(gè)鏈表的翻轉(zhuǎn)過程绘趋。如果不理解自己動(dòng)手畫一下可能更好理解哈颤陶，注意在畫的時(shí)候一次只考慮一個(gè)節(jié)點(diǎn)，且不要考慮已經(jīng)翻轉(zhuǎn)完的鏈表部分埋心。

下面我們來看下實(shí)現(xiàn)過程：

public Node  reverseList(Node head){
   //頭節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)為 null
   Node pre = null;
   Node next = null;
   
   while(head != null){
       next = head.next;
       head.next = pre;
       pre = head;
       head = next;
   }
}

翻轉(zhuǎn)部分單鏈表

題目要求：要求 0 < from < to < len 如果不滿足則不翻轉(zhuǎn)

這類題還有一類進(jìn)階題型指郁，就是翻轉(zhuǎn)鏈表 from 位置到 to 位置的節(jié)點(diǎn)，其實(shí)翻轉(zhuǎn)過程是相似的拷呆，只是我們需要找到位于 from 的前一個(gè)節(jié)點(diǎn)闲坎，和 to 的下一個(gè)節(jié)點(diǎn) 翻轉(zhuǎn)完 from 和 to 部分后將 from 的上一個(gè)節(jié)點(diǎn)的 next 指針指向翻轉(zhuǎn)后的to，將翻轉(zhuǎn)后 from 節(jié)點(diǎn)的 next 指針指向 to 節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)茬斧。

遍歷整個(gè)鏈表遍歷過程需要統(tǒng)計(jì)鏈表的長度 len 腰懂，from 節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) fPosPre , 翻轉(zhuǎn)開始的節(jié)點(diǎn) from ，翻轉(zhuǎn)結(jié)束的節(jié)點(diǎn) to 项秉，節(jié)點(diǎn)to 節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn) tPosNext 绣溜。
循環(huán)后判斷條件 0 < from < to < len 的條件是否滿足，如果不滿足返回 head
進(jìn)行 from 到 to 節(jié)點(diǎn)翻轉(zhuǎn)
翻轉(zhuǎn)完后判斷如果翻轉(zhuǎn)的起點(diǎn)不是 head 則返回 head,如果反轉(zhuǎn)的鏈表是起點(diǎn)娄蔼，那么翻轉(zhuǎn)后 toPos 就是頭結(jié)點(diǎn)怖喻。

下面我們開看代碼(你可能有更簡便的解法，省去幾個(gè)變量岁诉，但是下面的解法應(yīng)該是最好理解的);


    private Node reversePartList(Node head, int from, int to) {
        
        Node dummyHead = head;

        int len = 0;

        Node fPosPre = null;
        Node tPosNext = null;
        Node toPos = null;
        Node fromPos = null;

        while (dummyHead != null) {
            //因?yàn)?len = 0 開始的所以 len 先做自增一
            len++;

            if (len == from) {
                fromPos = dummyHead;
            } else if (len == from - 1) {
                fPosPre = dummyHead;
            } else if (len == to + 1) {
                tPosNext = dummyHead;
            } else if (len == to) {
                toPos = dummyHead;
            }

            dummyHead = dummyHead.next;
        }

        //不滿足條件不翻轉(zhuǎn)鏈表
        if (from > to || from < 0 || to > len || from > len) {
            return head;
        }


        Node cur = fromPos;
        Node pre = tPosNext;
        Node next = null;

        while (cur != null && cur != tPosNext) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 如果翻轉(zhuǎn)的起點(diǎn)不是 head 則返回 head
        if (fPosPre != null) {
            fPosPre.next = pre;
            return head;
        }
        // 如果反轉(zhuǎn)的鏈表是起點(diǎn)锚沸，那么翻轉(zhuǎn)后 toPos 就是頭結(jié)點(diǎn)
        return toPos;
    }

單鏈表排序

在我的上一篇文章中說到了數(shù)組基本的排序方法搞懂基本排序方法，對(duì)于鏈表來說也有上述幾種排序方法涕癣，如果感興趣的朋友也可以使用冒泡排序哗蜈，選擇排序，快速排序去實(shí)現(xiàn)單鏈表的排序坠韩，由于鏈表的不可回溯行距潘，對(duì)于鏈表來說歸并排序是個(gè)不錯(cuò)的排序方法。我們知道歸并通過遞歸只搁，可以實(shí)現(xiàn)音比，那么對(duì)于單鏈表來說也是可以的。

單鏈表的歸并排序

歸并的中心思想在于在于已知兩個(gè)鏈表的時(shí)候氢惋，如果按順序歸并這兩個(gè)鏈表硅确。其實(shí)這也是一道面試題按照元素的大小合并兩個(gè)鏈表那么我們就先看下如何合并兩個(gè)鏈表我們稱這個(gè)過程為 merge 。

private Node merge(Node l, Node r) {

   //創(chuàng)建臨時(shí)空間
   Node aux = new Node();
   Node cur = aux;

   //由于鏈表不能方便的拿到鏈表長度 所以一般使用 while l == null 表示鏈表遍歷到尾部
   while (l != null && r != null) {
       if (l.value < r.value) {
           cur.next = l;
           cur = cur.next;
           l = l.next;
       } else {
           cur.next = r;
           cur = cur.next;
           r = r.next;
       }
   }
   //當(dāng)有一半鏈表遍歷完成后 另外一個(gè)鏈表一定只剩下最后一個(gè)元素（鏈表為基數(shù)）
   if (l != null) {
       cur.next = l;
   } else if (r != null) {
       cur.next = r;
   }

   return aux.next;
}

返回的 Node 節(jié)點(diǎn)為歸并完成后的鏈表頭節(jié)點(diǎn)明肮。那么歸并排序的核心過程也完成了，想想我們想要?dú)w并一個(gè)數(shù)組還需要一個(gè)劃分操作 中心節(jié)點(diǎn) mid 是誰缭付，看到這里是不是笑了柿估，之前我們已經(jīng)講過如何尋找一個(gè)鏈表的中間元素，那么是不是萬事具備了陷猫，ok 我們來實(shí)現(xiàn)鏈表的歸并排序：

private Node mergeSort(Node head) {

   //遞歸退出的條件 當(dāng)歸并的元素為1個(gè)的時(shí)候 即 head.next 退出遞歸
   if (head == null || head.next == null) {
       return head;
   }

   Node slow = head;
   Node fast = head;

   //尋找 mid 值
   while (fast.next != null && fast.next.next != null) {
       slow = slow.next;
       fast = fast.next.next;
   }

   Node left = head;
   Node right = slow.next;

   //拆分兩個(gè)鏈表 如果設(shè)置鏈表的最后一個(gè)元素指向 null 那么 left 永遠(yuǎn)等于 head 這鏈表 也就無法排序
   slow.next = null;
   
   //遞歸的劃分鏈表
   left = mergeSort(left);
   right = mergeSort(right);

   return merge(left, right);
}

單鏈表的插入排序

回想一下數(shù)組的插入排序秫舌，我們從第二個(gè)數(shù)開始遍歷數(shù)組的妖，如果當(dāng)前考察的元素值比下一個(gè)元素的值要大，則下一個(gè)元素應(yīng)該排列排列在當(dāng)前考察的元素之前足陨，所以我們從已經(jīng)排序的元素序列中從后向前掃描嫂粟，如果該元素（已排序）大于新元素，將該元素移到下一位置（賦值也好墨缘，交換位置也好）星虹。但是由于鏈表的不可回溯性，我們只能從鏈表的頭節(jié)點(diǎn)開始找镊讼，這個(gè)元素應(yīng)該要在的位置宽涌。

我們來看下代碼實(shí)現(xiàn)：

    public Node insertionSortList(Node head) {
        if (head == null || head.next == null) return head;

        Node dummyHead = new Node(0)；
        Node p = head;
        dummyHead.next = head;
      //p 的值不小于下一節(jié)點(diǎn)元素考察下一節(jié)點(diǎn)
        while (p.next != null) {
            if (p.value <= p.next.value) { 
                p = p.next;
            } else {
                //p 指向 4
                Node temp = p.next;
                Node q = dummyHead;
                p.next = p.next.next;

                //從頭遍歷鏈表找到比當(dāng)前 temp 值小的第一個(gè)元素插入其后邊 整個(gè)位置一定在 頭節(jié)點(diǎn)與 q 節(jié)點(diǎn)之間
                while (q.next.value < temp.value && q.next != q)
                    q = q.next;

                temp.next = q.next;
                //重新連接鏈表 注意 else 的過程并沒有改變 p 指針的位置
                q.next = temp;
            }
        }
        return dummyHead.next;
    }

劃分鏈表

題目：按某個(gè)給定值將鏈表劃分為左邊小于這個(gè)值蝶棋，右邊大于這個(gè)值的新鏈表如一個(gè)鏈表為 1 -> 4 -> 5 -> 2 給定一個(gè)數(shù) 3 則劃分后的鏈表為 1-> 2 -> 4 -> 5

此題不是很難卸亮，就是遍歷一遍鏈表，就可以完成玩裙，我們新建一兩個(gè)鏈表兼贸，如果遍歷過程中，節(jié)點(diǎn)值比給定值小則劃在左鏈表中吃溅，反之放在右鏈表中溶诞，遍歷完成后拼接兩個(gè)鏈表就好。不做過多解釋直接看代碼罕偎。

 private Node partition(Node head , int x){
    if(head == null){
        return = null;
    }
    
    Node left = new Node(0);
    Node right = new Node(0);
    
    Node dummyLeft = left;
    Node dummyRight = right;
    
    while(head != null){
        if(head.value < x){
            dummyLeft.next = head;
            dummyLeft = dummyLeft.next;
        }else{
            dummyRight.next = head;
            dummyRight = dummyRight.next;
        }
        head = head.next;
    }
    
    dummyLeft.next = right.next;
    right.next = null;
    
    return left.next;
 }

鏈表相加求和

題目：假設(shè)鏈表中每一個(gè)節(jié)點(diǎn)的值都在 0-9 之間很澄，那么鏈表整體可以代表一個(gè)整數(shù)。
例如： 9->3->7 可以代表 937
給定兩個(gè)這樣的鏈表颜及，頭節(jié)點(diǎn)為 head1 head2 生成鏈表相加的新鏈表甩苛。
如 9->3->7 和 6 -> 3 生成的新鏈表應(yīng)為 1 -> 0 -> 0 -> 0

此題如果明白題意的情況并不難解決，首先理解怎么取加兩個(gè)鏈表俏站，即鏈表按照讯蒲，尾節(jié)點(diǎn)往前的順序每一位相加，如果有進(jìn)位則在下一個(gè)節(jié)點(diǎn)相加的時(shí)候算上肄扎，每一位加和為新鏈表的一個(gè)結(jié)點(diǎn)墨林。這看上去跟數(shù)學(xué)加法一樣。所以我們的解題思路為：

翻轉(zhuǎn)要相加的兩個(gè)鏈表犯祠，這樣就可以從原鏈表的尾節(jié)點(diǎn)開始相加旭等。
同步遍歷兩個(gè)逆序鏈表，每一個(gè)節(jié)點(diǎn)的值相加衡载，通過是要使用變量記錄是否進(jìn)位搔耕。
當(dāng)鏈表遍歷完成后判斷是否還有進(jìn)位如果有再添加一個(gè)結(jié)點(diǎn)，
再次翻轉(zhuǎn)兩個(gè)鏈表使其復(fù)原痰娱，并翻轉(zhuǎn)新鏈表弃榨，則得到的題解菩收。


private Node addLists(Node head1, Node head2) {
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        //進(jìn)位標(biāo)識(shí)
        int ca = 0;
        int n1 = 0;
        int n2 = 0;
        int sum = 0;

        Node addHead = new Node(0);
        Node dummyHead = addHead;

        Node cur1 = head1;
        Node cur2 = head2;

        while (cur1 != null || cur2 != null) {
            n1 = cur1 == null ? 0 : cur1.value;
            n2 = cur2 == null ? 0 : cur2.value;

            sum = n1 + n2 + ca;

            Node node = new Node(sum % 10);
            System.out.println( sum % 10);
            ca = sum / 10;

            dummyHead.next = node;

            dummyHead = dummyHead.next;

            cur1 = cur1 == null ? null : cur1.next;
            cur2 = cur2 == null ? null : cur2.next;
        }

        if (ca > 0) {
            dummyHead.next = new Node(ca);
        }

        head1 = reverseList(head1);
        head2 = reverseList(head2);

        addHead = addHead.next;
        return reverseList(addHead);
    }
    
    private  Node reverseList(Node head) {
        Node cur = head;
        Node pre = null;
        Node next = null;

        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //注意這里返回的是賦值當(dāng)前比較元素
        return pre;
    }

刪除有序/無序鏈表中重復(fù)的元素

刪除有序鏈表中的重復(fù)元素

刪除有序鏈表中的重復(fù)元素比較簡單，因?yàn)殒湵肀旧碛行蚓ňΓ匀绻刂抵貜?fù)娜饵，那么必定相鄰，所以刪除重復(fù)元素的方法為:

如一個(gè)鏈表為 36 -> 37 -> 65 -> 76 -> 97 -> 98 -> 98 -> 98 -> 98 -> 98
刪除重復(fù)元素后為: 36 -> 37 -> 65 -> 76 -> 97 -> 98

 private void delSortSame(Node head) {
        if (head == null || head.next == null) {
            return;
        }

        Node dummy = head;
        while (dummy.next != null) {
            if (dummy.value == dummy.next.value) {
                dummy.next = dummy.next.next;
            } else {
                dummy = dummy.next;
            }
        }
    }

刪除無序鏈表中的重復(fù)元素

刪除無序鏈表中的重復(fù)元素官辈，就要求我們必須使用一個(gè)指針記住當(dāng)前考察元素 cur 的上一個(gè)元素 pre 箱舞，并以此遍歷考察元素之后的所有節(jié)點(diǎn)，如果有重復(fù)則將 pre 指針的 next 指針指向當(dāng) cur.next; 重復(fù)遍歷每個(gè)節(jié)點(diǎn)钧萍，直至鏈表結(jié)尾褐缠。

如一個(gè)鏈表刪除重復(fù)元素前為: 0 -> 0 -> 3 -> 5 -> 3 -> 0 -> 1 -> 4 -> 5 -> 7
刪除重復(fù)元素后為: 0 -> 3 -> 5 -> 1 -> 4 -> 7

private void delSame(Node head) {

   if (head == null || head.next == null) {
       return;
   }
   
   Node pre = null;
   Node next = null;
   Node cur = head;

   while (cur != null) {
       //當(dāng)前考察的元素的前一個(gè)節(jié)點(diǎn)
       pre = cur;
       //當(dāng)前考察元素
       next = cur.next;
       //從遍歷剩余鏈表刪除重復(fù)元素
       while (next != null) {
           if (cur.value == next.value) {
               //刪除相同元素
               pre.next = next.next;
           }else {
               //移動(dòng)指針
               pre = next;
           }
           //移動(dòng)指針
           next = next.next;
       }
       //考察下一個(gè)元素
       cur = cur.next;
   }
}

重排鏈表

其實(shí)這也是一系列的題目，主要考察了我們對(duì)于額外空間復(fù)雜度為O(1) 的鏈表操作风瘦。我們先看第一道題：

按照左右半?yún)^(qū)的方式重新排列組合單鏈表

題目給定一個(gè)單鏈表L： L0→L1→…→Ln-1→Ln, 重新排列后為 L0→Ln→L1→Ln-1→L2→Ln-2→… 要求必須在不改變節(jié)點(diǎn)值的情況下進(jìn)行原地操作队魏。

我們先來分析一下題目，要想重排鏈表万搔，必須先找到鏈表的中間節(jié)點(diǎn)胡桨，然后分離左右兩部鏈表，然后按左邊一個(gè)瞬雹，右邊一個(gè)的順序排列鏈表昧谊。我們假設(shè)鏈表為基數(shù)的時(shí)候， N/2 位置的節(jié)點(diǎn)算左半鏈表酗捌，那么右半鏈表就會(huì)比左半鏈表多一個(gè)節(jié)點(diǎn)呢诬。當(dāng)左半鏈表為最后一個(gè)節(jié)點(diǎn)的時(shí)候我們只需要將剩余的右半鏈表設(shè)為其下一個(gè)節(jié)點(diǎn)即可。 N 為偶數(shù)的時(shí)候就好說了胖缤，N/2 + 1 為右半鏈表的開始尚镰，重拍最后只需要將左半鏈表為最后一個(gè)節(jié)點(diǎn)指向 null，恰巧此時(shí)右半鏈表為 null 所以重拍最后一步就是 left.next = right 下面我們來看題解：


private void relocate1(Node head) {
   //如果鏈表長度小于2 則不需要重新操作
   if (head == null || head.next == null) {
       return;
   }

   //使用快慢指針 遍歷鏈表找到鏈表的中點(diǎn)
   Node mid = head;
   Node right = head.next;

   while (right.next != null && right.next.next != null) {
       mid = mid.next;
       right = right.next.next;
   }

   //拆分左右半?yún)^(qū)鏈表
   right = mid.next;
   mid.next = null;

   //按要求合并
   mergeLR(head, right);

}

private void mergeLR(Node left, Node right) {
   Node temp = null;
   while (left.next != null) {
       temp = right.next;

       right.next = left.next;
       left.next = right;

       //這里每次向后移動(dòng)兩個(gè)位置 也就是原來的 left.next
       left = right.next;
       right = temp;
   }
   left.next = right;
}

今日頭條的一個(gè)重排鏈表題目

給定一個(gè)鏈表 1 -> 92 -> 8 -> 86 -> 9 -> 43 -> 20 鏈表的特征是奇數(shù)位升序哪廓，偶數(shù)位為降序狗唉，要求重新排列鏈表并保持鏈表整體為升序

這道題和左右半?yún)^(qū)重排鏈表類似，其實(shí)這可以理解為一個(gè)已經(jīng)進(jìn)行重排后的鏈表涡真，現(xiàn)在要執(zhí)行上一道重排的逆過程分俯。要滿足這個(gè)條件，我們必須假設(shè)偶數(shù)位最小的節(jié)點(diǎn)大于奇數(shù)位最大的元素哆料。我想出題人也是這意思缸剪。如果不是的話也不麻煩上邊我們也講了歸并排序的方法，只是一次歸并而已东亦。下面來看滿足數(shù)位最小的節(jié)點(diǎn)大于奇數(shù)位最大的元素的解法：

此題考察了面試者對(duì)鏈表的基本操作以及如何翻轉(zhuǎn)一個(gè)鏈表

 private Node relocate2(Node head) {

        //新建一個(gè)左右連個(gè)鏈表的頭指針
        Node left = new Node();
        Node right = new Node();


        Node dummyLeft = left;
        Node dummyRight = right;

        int i = 0;
        while (head != null) {
            //因?yàn)?i 從0 開始 鏈表的頭節(jié)點(diǎn)算是奇數(shù)位所以 i 先自增 再比較
            i++;
            if (i % 2 == 0) {
                dummyRight.next = head;
                dummyRight = dummyRight.next;
            } else {
                dummyLeft.next = head;
                dummyLeft = dummyLeft.next;
            }
            //每次賦值后記得將下一個(gè)節(jié)點(diǎn)置位 null
            Node next = head.next;
            head.next = null;
            head = next;
        }

        right = reverseList(right.next);
        dummyLeft.next = right;

        return left.next;
    }

判斷兩個(gè)單鏈表（無環(huán)）是相交

題目：判斷兩個(gè)無環(huán)鏈表是否相交杏节，如果相交則返回第一個(gè)相交節(jié)點(diǎn)，如果不想交返回 null 。

我們來分析一下這道題拢锹，我們假設(shè)兩個(gè)單鏈表相交，那從相交的節(jié)點(diǎn)開始到結(jié)束萄喳，一直到兩個(gè)鏈表都結(jié)束卒稳，那么后邊這段鏈表相當(dāng)于是共享的。我們還可以知道如果將這兩個(gè)鏈表的末尾對(duì)齊他巨，這兩個(gè)鏈表的尾節(jié)點(diǎn)一定是相等的充坑，所以我們的解題思路如下：

想讓一個(gè)鏈表遍歷一遍，并記錄其長度
在遍歷另一個(gè)鏈表染突，遍歷過程中 n 每次自減一
遍歷結(jié)束后捻爷，指針 cur1 指向鏈表 head1 的最后一個(gè)節(jié)點(diǎn)，同理指針 cur2 指向 head2 的最后一個(gè)節(jié)點(diǎn)份企，如果此時(shí) cur1 != cur2 那么根據(jù)題意這兩個(gè)鏈表不想交也榄。
遍歷結(jié)束后，我們假設(shè) hea1 要比 head2 長司志，那么 n 一定為正數(shù)甜紫，代表了 head1 頭節(jié)點(diǎn)指針如果向右移動(dòng) n 個(gè)數(shù) 剩余鏈表的長度將和 head2 一樣長
此后 point1 和 point2 一起走那么這兩個(gè) point 指向的節(jié)點(diǎn)總會(huì)相等，第一次相等的點(diǎn)即為兩個(gè)鏈表相交的點(diǎn)骂远。

 private Node intersect(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        Node cur1 = head1;
        Node cur2 = head2;

        int n = 0;

        while (cur1.next != null) {
            n++;
            cur1 = cur1.next;
        }

        while (cur2.next != null) {
            n--;
            cur2 = cur2.next;
        }

        if (cur1 != cur2) {
            return null;
        }

        //令 cur1 指向 較長的鏈表囚霸，cur2 指向較短的鏈表
        if (n > 0) {
            cur1 = head1;
            cur2 = head2;
        } else {
            cur1 = head2;
            cur2 = head1;
        }

        n = Math.abs(n);

        //較長的鏈表先走 n 步
        while (n != 0) {
            cur1 = cur1.next;
        }

        //兩個(gè)鏈表一起走 第一次相等節(jié)點(diǎn)即為相交的第一個(gè)節(jié)點(diǎn)
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        
        return cur1;
    }

總結(jié)

上篇文章搞懂排序算法評(píng)論有人說，文章太長了激才。沒想到這篇文章寫著寫著又這么長了拓型。還請(qǐng)大家耐下心來看，每到題自己耐下心來做一遍瘸恼。等大家都搞懂以后劣挫，相信大家也就差不多無所畏懼單鏈表的面試題了。

歡迎大家關(guān)注我的個(gè)人博客地址钞脂，本文算法題也上傳到我的 github上了揣云。NodePractice 后續(xù)我將開始學(xué)習(xí)數(shù)組，和字符串的算法題冰啃。相信不久將來又能見到我的又臭又長的文章了邓夕。

最后 愿天不負(fù)有心人。

最后編輯于：2018.03.09 23:25:02

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末阎毅，一起剝皮案震驚了整個(gè)濱河市焚刚，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌扇调，老刑警劉巖矿咕，帶你破解...
沈念sama閱讀 206,968評(píng)論 6贊 482
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異，居然都是意外死亡碳柱，警方通過查閱死者的電腦和手機(jī)捡絮，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,601評(píng)論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來莲镣，“玉大人福稳，你說我怎么就攤上這事∪鹞辏” “怎么了的圆？”我有些...
開封第一講書人閱讀 153,220評(píng)論 0贊 344
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長半火。經(jīng)常有香客問我越妈，道長，這世上最難降的妖魔是什么钮糖？我笑而不...
開封第一講書人閱讀 55,416評(píng)論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任梅掠，我火速辦了婚禮，結(jié)果婚禮上藐鹤，老公的妹妹穿的比我還像新娘瓤檐。我一直安慰自己，他們只是感情好娱节，可當(dāng)我...
茶點(diǎn)故事閱讀 64,425評(píng)論 5贊 374
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布挠蛉。她就那樣靜靜地躺著，像睡著了一般肄满。火紅的嫁衣襯著肌膚如雪谴古。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,144評(píng)論 1贊 285
城市分裂傳說
那天稠歉，我揣著相機(jī)與錄音掰担，去河邊找鬼。笑死怒炸，一個(gè)胖子當(dāng)著我的面吹牛带饱，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播阅羹，決...
沈念sama閱讀 38,432評(píng)論 3贊 401
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼勺疼，長吁一口氣：“原來是場噩夢(mèng)啊……” “哼！你這毒婦竟也來了捏鱼？” 一聲冷哼從身側(cè)響起执庐，我...
開封第一講書人閱讀 37,088評(píng)論 0贊 261
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎导梆，沒想到半個(gè)月后轨淌，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體迂烁，經(jīng)...
沈念sama閱讀 43,586評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,028評(píng)論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年递鹉，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了盟步。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,137評(píng)論 1贊 334
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡躏结，死狀恐怖址芯，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情窜觉，我是刑警寧澤，帶...
沈念sama閱讀 33,783評(píng)論 4贊 324
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布北专，位于F島的核電站禀挫，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏拓颓。R本人自食惡果不足惜语婴，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,343評(píng)論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望驶睦。院中可真熱鬧砰左，春花似錦、人聲如沸场航。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,333評(píng)論 0贊 19
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽溉痢。三九已至僻造，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間孩饼，已是汗流浹背髓削。一陣腳步聲響...
開封第一講書人閱讀 31,559評(píng)論 1贊 262
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留镀娶，地道東北人立膛。一個(gè)月前我還...
沈念sama閱讀 45,595評(píng)論 2贊 355
代替公主和親
正文我出身青樓，卻偏偏與公主長得像梯码，于是被迫代替她去往敵國和親宝泵。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,901評(píng)論 2贊 345

搞懂單鏈表常見面試題

搞懂單鏈表常見面試題

什么是單鏈表

單鏈表的基本操作

獲取單鏈表的長度

查詢指定索引的節(jié)點(diǎn)值或指定值得節(jié)點(diǎn)值的索引

鏈表添加一個(gè)元素

鏈表刪除一個(gè)元素

單鏈表常見面試題

尋找單鏈表的中間元素

判斷一個(gè)鏈表是否是循環(huán)鏈表

已知一個(gè)單鏈表求倒數(shù)第 N 個(gè)節(jié)點(diǎn)

刪除單鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)

旋轉(zhuǎn)單鏈表

翻轉(zhuǎn)單鏈表

翻轉(zhuǎn)部分單鏈表

單鏈表排序

單鏈表的歸并排序

單鏈表的插入排序

劃分鏈表

鏈表相加求和

刪除有序/無序鏈表中重復(fù)的元素

刪除有序鏈表中的重復(fù)元素

刪除無序鏈表中的重復(fù)元素

重排鏈表

按照左右半?yún)^(qū)的方式重新排列組合單鏈表

今日頭條的一個(gè)重排鏈表題目

判斷兩個(gè)單鏈表（無環(huán)）是相交

總結(jié)

推薦閱讀更多精彩內(nèi)容