4.5 雙向鏈表和循環鏈表

由于單向鏈表只能從頭節點開始遍歷到尾節點，遍歷的順序受到限制，在很多場景下使用起來不是很方便，因此雙向鏈表應運而生。雙向鏈表在單向鏈表節點的基礎上增加了指向前一個節點的指針，這樣一來，既可以從頭節點開始從前往后遍歷到尾節點，也可以從尾節點開始從后往前遍歷到頭節點。

由于雙向鏈表的每個節點多了一個指針，因此在雙向鏈表中添加、刪除節點等操作要稍微復雜一點。如果應聘者遇到雙向鏈表的面試題，就要格外小心，確保節點的每個指針都指向了正確的位置。

如果把鏈表尾節點指向下一個節點的指針指向鏈表的頭節點，那么此時鏈表就變成一個循環鏈表，相當于循環鏈表的所有節點都位于一個環中。循環鏈表既可以是單向鏈表也可以是雙向鏈表。即使一個循環鏈表是單向鏈表，也可以從任意節點出發到達另一個任意節點，因此，在循環鏈表中任意節點都可以當作鏈表的頭節點。

面試題28：展平多級雙向鏈表

分析：在面試時如果遇到這種類型的題目，應聘者需要先弄清楚展平的規則。在圖4.14的示例中，節點2有一個子鏈表，展平之后該子鏈表插入節點2和它的下一個節點3之間。節點6也有一個子鏈表，展平之后該子鏈表插入節點6和它的下一個節點7之間。由此可知，展平的規則是一個節點的子鏈展平之后將插入該節點和它的下一個節點之間。

由于子鏈表中的節點也可能有子鏈表，因此這里的鏈表是一個遞歸的結構。在展平子鏈表時，如果它也有自己的子鏈表，那么它嵌套的子鏈表也要一起展平。嵌套子鏈表和外層子鏈表的結構類似，可以用同樣的方法展平，因此可以用遞歸函數來展平鏈表。遞歸代碼如下所示：

在上述代碼中，遞歸函數flattenGetTail在展平以head為頭節點的鏈表之后返回鏈表的尾節點。在該函數中需要逐一掃描鏈表中的節點。如果一個節點node有子鏈表，由于子鏈表也可能有嵌套的子鏈表，因此先遞歸調用flattenGetTail函數展平子鏈表，子鏈表展平之后的頭節點是child，尾節點是childTail。最后將展平的子鏈表插入節點node和它的下一個節點next之間，即把展平的子鏈表的頭節點child插入節點node之后，并將尾節點childTail插入節點next之前。

這種解法每個節點都會遍歷一次，如果鏈表總共有n個節點，那么時間復雜度是O（n）。函數flattenGetTail的遞歸調用次數取決于鏈表嵌套的層數，因此，如果鏈表的層數為k，那么該節點的空間復雜度是O（k）。

面試題29：排序的循環鏈表

分析：首先分析在排序的循環鏈表中插入節點的規律。當在圖4.15（a）的鏈表中插入值為4的節點時，新的節點位于值為3的節點和值為5的節點之間。這很容易理解，為了使插入新節點的循環鏈表仍然是排序的，新節點的前一個節點的值應該比新節點的值小，后一個節點的值應該比新節點的值大。

但是特殊情況需要特殊處理。如果新節點的值比鏈表中已有的最大值還要大，那么新的節點將被插入最大值和最小值之間。例如，如果在圖4.15（a）中插入值為7的節點，那么新節點位于原來值最大的節點和值最小的節點之間，如圖4.16（a）所示。

新節點的值比鏈表中已有的最小值還要小的情形和前面類似，新的節點也將被插入最大值和最小值之間。例如，在圖4.15（a）中插入值為0的節點，新節點也位于原來值最大的節點和值最小的節點之間，如圖4.16（b）所示。

下面總結在排序的循環鏈表中插入新節點的規則。先試圖在鏈表中找到相鄰的兩個節點，如果這兩個節點的前一個節點的值比待插入的值小并且后一個節點的值比待插入的值大，那么就將新節點插入這兩個節點之間。如果找不到符合條件的兩個節點，即待插入的值大于鏈表中已有的最大值或小于已有的最小值，那么新的節點將被插入值最大的節點和值最小的節點之間。

在上面的規則中，總是先試圖從鏈表中找到符合條件的相鄰的兩個節點。如果開始的時候鏈表中的節點數小于2，那么應該有兩種可能。第1種可能是開始的時候鏈表是空的，一個節點都沒有。此時插入一個新的節點，該節點成為循環鏈表中的唯一節點，那么next指針指向節點自己，如圖4.17（a）所示。第2種可能是開始的時候鏈表中只有一個節點，插入一個新的節點之后，兩個節點的next指針互相指向對方，如圖4.17（b）所示。

將插入規則和各種邊界條件都考慮清楚之后就可以開始編寫代碼。參考代碼如下所示：

在函數insert中先處理鏈表是空的或鏈表中只有一個節點的情況，然后調用函數insertCore處理鏈表中的節點數超過一個的情況。在函數insertCore中試圖找到相鄰的兩個節點cur和next，使cur的值小于或等于待插入的值且next的值大于或等于待插入的值。如果找到了就將新節點插入它們之間。如果沒有找到符合條件的兩個節點，就將新的節點插入值最大的節點biggest的后面。