鏈表是最基本的數(shù)據(jù)結(jié)構(gòu)闸迷，面試官也常常用鏈表來考察面試者的基本能力士败，而且鏈表相關(guān)的操作相對而言比較簡單闯两，也適合考察寫代碼的能力。鏈表的操作也離不開指針谅将，指針又很容易導(dǎo)致出錯生蚁。綜合多方面的原因，鏈表題目在面試中占據(jù)著很重要的地位戏自。

1. 單向鏈表的定義

想必大家對數(shù)組都非常熟悉，數(shù)組在存儲空間（內(nèi)存）上是連續(xù)的伤锚。因此擅笔，我們可以根據(jù)偏移量輕易的找到數(shù)組中的數(shù)據(jù)。但數(shù)組最大的問題是大小是固定的屯援，很多場景是無法預(yù)判需要的空間大小的猛们。

1.1 什么是單向鏈表

鏈表也是一種線性數(shù)據(jù)結(jié)構(gòu)，但它最大的優(yōu)勢是可以動態(tài)的調(diào)整大小狞洋。這樣弯淘，我們再也不用擔(dān)心應(yīng)該分配多少空間了。

鏈表是一種物理存儲單元上非連續(xù)吉懊、非順序的存儲結(jié)構(gòu)庐橙，元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的

鏈表在日常開發(fā)中通常通過數(shù)據(jù)結(jié)構(gòu)和指針的方式實現(xiàn)，其中包含一個本數(shù)據(jù)結(jié)構(gòu)的next指針借嗽，用于指向下一個元素态鳖，這樣指下去，就形成了一個單向鏈表恶导。如下是數(shù)據(jù)結(jié)構(gòu)的定義：

struct list_node
{
        void *data;             /* 存儲的數(shù)據(jù)浆竭，通過void指針，可以適配多種數(shù)據(jù)類型 */
        struct list_node *next; /* 指向下一個節(jié)點，如果為尾節(jié)點則指向NULL */
};

為了便于鏈表的管理和使用邦泄，我們在實際定義的時候通常還會定義個專門的鏈表頭删窒，鏈表頭的定義如下：

struct list
{
        int size;
        void (*print_node)(void *data);
        struct list_node *head;
        struct list_node *tail;
};

通過增加一個鏈表頭可以方便鏈表的管理，同時通過增加的元數(shù)據(jù)可以很方便的得到一些鏈表的信息顺囊，從而提高效率肌索。這樣，整個鏈表的結(jié)構(gòu)大概如圖1所示包蓝。

圖1 單向鏈表示意圖

1.2 單向鏈表的接口

單向鏈表最主要的接口就是初始化驶社、插入元素和刪除元素等操作了。當(dāng)然测萎，為了方便使用亡电，還有返回鏈表頭元素，鏈表尾元素和鏈表大小等等硅瞧。我們這里先看一下幾個主要的函數(shù)接口份乒。

/*  初始化鏈表 */
void list_init(struct list *list, void (*print_node)(void *data));
/* 向鏈表中添加一個元素，其中node為插入的位置腕唧，也就是
   插到該元素的后面或辖，如果node為NULL則插到首節(jié)點。  */
int list_insert_next(struct list *list, struct list_node *node, void *data);
int list_rem_next(struct list *list, struct list_node *node, void **data);

下面我們給出插入操作的代碼實現(xiàn)枣接，其它操作類似颂暇，也比較簡單，這里就不羅列代碼了但惶。具體可以參考本文的配套github庫耳鸯。

int list_insert_next(struct list *list, 
                     struct list_node *node,
                     void *data)
{
        struct list_node *new_node;

        if (NULL == list) {
                return -1;
        }       

        new_node = (struct list_node*)malloc(sizeof(struct list_node));
        if (NULL == new_node) {
                return -1;
        }

        new_node->data = data;
        if (NULL == node) {
                if (list_size(list) == 0)
                        list->tail = new_node;
                new_node->next = list->head;
                list->head = new_node;          
        } else {
                if (NULL == node->next) {
                        list->tail = new_node;
                }
                new_node->next = node->next;
                node->next = new_node;
        }

        list->size ++;
        return 0;
}

2. 單向鏈表的算法（面試題）

關(guān)于單向鏈表的面試題很多，我們這里盡量的都收集過來膀曾。目前有些復(fù)雜的沒有答案县爬，但我們后續(xù)會陸續(xù)寫文章將答案收集起來。

2.1 求單鏈表中結(jié)點的個數(shù)

這個題目是比較簡單的添谊，基本做法就是對單向鏈表進(jìn)行遍歷财喳。在進(jìn)行遍歷的時候有一個計數(shù)的變量，每遍歷一個節(jié)點斩狱，計數(shù)增1耳高，直到完成鏈表的遍歷。

int list_node_count(struct list *list)
{
        int ret = 0;
        struct list_node *cur_node;
        /* 注意list指針非法的情況 */
        if (NULL == list) {
                return ret;
        }   

        cur_node = list->head;
        while (cur_node) {
                ret ++; 
                cur_node = cur_node->next;
        }   
        return ret;
}

2.2 單鏈表反轉(zhuǎn) (leetcode 206)

將鏈表中的節(jié)點指向反過來喊废，比如原來的指向為1->2->3->4->5祝高，那么反轉(zhuǎn)后為5->4->3->2->1。鏈表反轉(zhuǎn)其實是調(diào)整節(jié)點的next指針的指向污筷。具體如圖所示工闺。

圖2 鏈表反轉(zhuǎn)示意圖

2.3 截取出單鏈表中的后K個結(jié)點（k>0）

2.4 判斷一個單鏈表中是否有環(huán)(若帶環(huán)乍赫，求環(huán)的長度和入口點)

2.5 去除有序鏈表中的重復(fù)元素(leetcode 83)

給定一個有序的鏈表，刪除所有重復(fù)的元素陆蟆，保證每個元素在鏈表中只出現(xiàn)一次雷厂。

2.6 合并兩個排好序的鏈表(leetcode 21)

2.7 鏈表的中間節(jié)點(leetcode 876)

給定一個帶有頭結(jié)點 head 的非空單鏈表，返回鏈表的中間結(jié)點叠殷。如果有兩個中間結(jié)點改鲫，則返回第二個中間結(jié)點。

輸入：[1,2,3,4,5]
輸出：此列表中的結(jié)點 3 (序列化形式：[3,4,5])
返回的結(jié)點值為 3 林束。 (測評系統(tǒng)對該結(jié)點序列化表述是 [3,4,5])像棘。

2.7 刪除鏈表中的節(jié)點 (leetcode 237)

請編寫一個函數(shù)，使其可以刪除某個鏈表中給定的（非末尾）節(jié)點壶冒。也就是你僅知道要求被刪除的節(jié)點缕题。

輸入: head = [4,5,1,9], node = 5
輸出: [4,1,9]

解釋: 給定你鏈表中值為 5 的第二個節(jié)點，那么在調(diào)用了你的函數(shù)之后胖腾，該鏈表應(yīng)變?yōu)?4 -> 1 -> 9.

鏈表至少包含兩個節(jié)點烟零。
鏈表中所有節(jié)點的值都是唯一的。
給定的節(jié)點為非末尾節(jié)點并且一定是鏈表中的一個有效節(jié)點咸作。
不要從你的函數(shù)中返回任何結(jié)果锨阿。

2.8 刪除鏈表的倒數(shù)第N個節(jié)點(leetcode 19)

給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?1->2->3->5.

2.9 刪除鏈表中的節(jié)點(leetcode 203)

題目
刪除鏈表中等于給定值 val 的所有節(jié)點记罚。
示例

輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5

2.10 約瑟夫環(huán)

約瑟夫環(huán)(約瑟夫問題)是一個數(shù)學(xué)的應(yīng)用問題：已知n個人(以編號1墅诡，2，3…n分別表示)圍坐在一張圓桌周圍桐智。從編號為k的人開始報數(shù)书斜，數(shù)到m的那個人出列;他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列;依此規(guī)律重復(fù)下去酵使，直到圓桌周圍的人全部出列。通常解決這類問題時我們把編號從0~n-1焙糟，最后結(jié)果+1即為原問題的解口渔。

2.11 遍歷一次，刪除倒數(shù)第 k 個結(jié)點（k從1開始）穿撮，不能用替換刪除法

2.12 將鏈表后k個節(jié)點移到鏈表頭

給一個鏈表和整數(shù)k缺脉，將后k個節(jié)點移到鏈表頭。

輸入： 1->2->3->4->5->NULL , k =2,
輸出： 4->5->1->2->3->NULL.

2.13 逆序打印單鏈表

2.14 不允許遍歷鏈表, 在 pos之前插入

2.15 單鏈表的冒泡排序

2.16 旋轉(zhuǎn)單鏈表

題目：給定一個鏈表悦穿，旋轉(zhuǎn)鏈表攻礼，使得每個節(jié)點向右移動k個位置，其中k是一個非負(fù)數(shù)栗柒。

輸入： 1->2->3->4->5->NULL 給定值 k = 2,
輸出： 4->5->1->2->3->NULL.

2.17 劃分鏈表

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

2.18 鏈表相加求和

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

2.19 重排鏈表

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