第六章 鏈表問題講解
鏈表（Linked List）是一種常見的基礎資料結構，是一種線性表，但是并不會按線性的順序存盤資料，而是在每一個節點里存到下一個節點的指標（Pointer），
由于不必須按順序存盤，鏈表在插入的時候可以達到 O(1)的復雜度，比另一種線性表 —— 順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要 O(n) 的時間，而順序表相應的時間復雜度分別是 O(n) 和 O(1)，
鏈表允許插入和移除表上任意位置上的節點，但是不允許隨機存取，鏈表有很多種不同的型別：單向鏈表，雙向鏈表以及回圈鏈表，
6.1 反轉鏈表（#206）
6.1.1 題目說明
反轉一個單鏈表，
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進階:
你可以迭代或遞回地反轉鏈表，你能否用兩種方法解決這道題？
6.1.2 分析
鏈表的節點結構ListNode已經定義好，我們發現，反轉鏈表的程序，其實跟val沒有關系，只要把每個節點的next指向之前的節點就可以了，
從代碼實作上看，可以有迭代和遞回兩種形式，
6.1.3 方法一：迭代
假設存在鏈表 1→2→3→null，我們想要把它改成null←1←2←3，
我們只需要依次迭代節點遍歷鏈表，在迭代程序中，將當前節點的 next 指標改為指向前一個元素就可以了，
代碼如下：
public class ReverseLinkedList {
public ListNode reverseList(ListNode head) {
ListNode curr = head;
ListNode prev = null;
// 依次迭代遍歷鏈表
while (curr != null){
ListNode tempNext = curr.next;
curr.next = prev;
prev = curr;
curr = tempNext;
}
return prev;
}
}復雜度分析
時間復雜度：O(n)，假設 n 是鏈表的長度，時間復雜度是 O(n)，
空間復雜度：O(1)，
6.1.4 方法二：遞回
遞回的核心，在于當前只考慮一個節點，剩下部分可以遞回呼叫，直接回傳一個反轉好的鏈表，然后只要把當前節點再接上去就可以了，
假設鏈表為（長度為m）：
n1 → n2 → …→nk?1 →nk →nk+1 →…→nm → null
若我們遍歷到了nk，那么認為剩余節點nk+1到nm 已經被反轉，
n1 → n2 → …→nk?1 →nk → nk+1 ←…← nm ?
我們現在希望 nk+1 的下一個節點指向 nk，所以，應該有
nk+1.next = nk
代碼如下：
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode restHead = head.next;
ListNode reversedRest = reverseList(restHead); // 遞回反轉
restHead.next = head;
head.next = null;
return reversedRest;
}復雜度分析
時間復雜度：時間復雜度：O(n)，假設 n 是鏈表的長度，那么時間復雜度為 O(n)，
空間復雜度：O(n)，由于使用遞回，將會使用隱式堆疊空間，遞回深度可能會達到 n 層，
6.2 合并兩個有序鏈表（#21）
6.2.1 題目說明
將兩個升序鏈表合并為一個新的升序鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
6.2.2 分析
鏈表節點結構已經定義好，而且已經做了升序排列，現在我們需要分別遍歷兩個鏈表，然后依次比較，按從小到大的順序生成新的鏈表就可以了，這其實就是“歸并排序”的思路，
6.2.3 方法一：迭代
最簡單的想法，就是逐個遍歷兩個鏈表中的節點，依次比對，
我們假設原鏈表為list1和list2，只要它們都不為空，就取出當前它們各自的頭節點就行比較，值較小的那個結點選取出來，加入到結果鏈表中，并將對應原鏈表的頭（head）指向下一個結點；而值較大的那個結點則保留，接下來繼續做比對，
另外，為了讓代碼更加簡潔，我們可以引入一個哨兵節點（sentinel），它的next指向結果鏈表的頭結點，它的值設定為-1，
代碼如下：
public class MergeTwoSortedLists {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//定義一個哨兵節點
ListNode resultPrev = new ListNode(-1);
ListNode prev = resultPrev;
// 遍歷兩個鏈表
while ( l1 != null && l2 != null ){
if ( l1.val <= l2.val ){
prev.next = l1;
prev = l1;
l1 = l1.next;
} else {
prev.next = l2;
prev = l2;
l2 = l2.next;
}
}
prev.next = (l1 == null) ? l2 : l1;
return resultPrev.next;
}
}復雜度分析
時間復雜度：O(n + m) ，其中 n 和 m 分別為兩個鏈表的長度，因為每次回圈迭代中，l1 和 l2 只有一個元素會被放進合并鏈表中， 因此 while 回圈的次數不會超過兩個鏈表的長度之和，所有其他操作的時間復雜度都是常數級別的，因此總的時間復雜度為 O(n+m)，
空間復雜度：O(1)，我們只需要常數的空間存放若干變數，
6.2.4 方法二：遞回
用遞回的方式同樣可以實作上面的程序，
當兩個鏈表都不為空時，我們需要比對當前兩條鏈的頭節點，取出較小的那個節點；而兩條鏈其余的部分，可以遞回呼叫，認為它們已經排好序，所以我們需要做的，就是把前面取出的那個節點，接到剩余排好序的鏈表頭節點前，
代碼如下：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if ( l1 == null )
return l2;
else if ( l2 == null )
return l1;
if ( l1.val <= l2.val ){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}復雜度分析
時間復雜度：O(n + m)，其中 nn 和 m 分別為兩個鏈表的長度，因為每次呼叫遞回都會去掉 l1 或者 l2 的頭節點（直到至少有一個鏈表為空），函式 mergeTwoList 至多只會遞回呼叫每個節點一次，因此，時間復雜度取決于合并后的鏈表長度，即 O(n+m)，
空間復雜度：O(n + m)，其中 n 和 m 分別為兩個鏈表的長度，遞回呼叫 mergeTwoLists 函式時需要消耗堆疊空間，堆疊空間的大小取決于遞回呼叫的深度，結束遞回呼叫時 mergeTwoLists 函式最多呼叫 n+m 次，因此空間復雜度為 O(n+m)，
6.3 洗掉鏈表的倒數第N個節點（#19）
6.3.1 題目說明
給定一個鏈表，洗掉鏈表的倒數第 n 個節點，并且回傳鏈表的頭結點，
示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當洗掉了倒數第二個節點后，鏈表變為 1->2->3->5.
說明：
給定的 n 保證是有效的，
進階：
你能嘗試使用一趟掃描實作嗎？
6.3.2 分析
在鏈表中洗掉某個節點，其實就是將之前一個節點next，直接指向當前節點的后一個節點，相當于“跳過”了這個節點，
當然，真正意義上的洗掉，還應該回收節點本身占用的空間，進行記憶體管理，這一點在java中我們可以不考慮，直接由JVM的GC幫我們實作，
6.3.3 方法一：計算鏈表長度（二次遍歷）
最簡單的想法是，我們首先從頭節點開始對鏈表進行一次遍歷，得到鏈表的長度 L，
然后，我們再從頭節點開始對鏈表進行一次遍歷，當遍歷到第 L-N+1 個節點時，它就是我們需要洗掉的倒數第N個節點，
這樣，總共做兩次遍歷，我們就可以得到結果，
代碼如下：
public class RemoveNthNodeFromEnd {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 遍歷鏈表，獲取長度
int l = getLength(head);
// 定義啞節點（哨兵）
ListNode sentinel = new ListNode(-1);
sentinel.next = head;
// 再次遍歷，找到倒數第N個
ListNode curr = sentinel;
for ( int i = 0; i < l - n; i++ ){
curr = curr.next;
}
curr.next = curr.next.next;
return sentinel.next;
}
// 定義一個獲取鏈表長度的方法
public static int getLength(ListNode head){
int length = 0;
while ( head != null ){
length ++;
head = head.next;
}
return length;
}
}復雜度分析
時間復雜度：O(L)，其中 L 是鏈表的長度，只用了兩次遍歷，是線性時間復雜度，
空間復雜度：O(1)，
6.3.4 方法二：利用堆疊
另一個思路是利用堆疊資料結構，因為堆疊是“先進后出”的，所以我們可以在遍歷鏈表的同時將所有節點依次入堆疊，然后再依次彈出，
這樣，彈出堆疊的第 n 個節點就是需要洗掉的節點，并且目前堆疊頂的節點就是待洗掉節點的前驅節點，這樣一來，洗掉操作就變得十分方便了，
代碼如下：
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode sentinel = new ListNode(-1);
sentinel.next = head;
// 定義堆疊
Stack<ListNode> stack = new Stack<>();
ListNode curr = sentinel;
// 遍歷鏈表，所有節點入堆疊
while ( curr != null ){
stack.push(curr);
curr = curr.next;
}
// 依次彈堆疊，彈出N個
for ( int i = 0; i < n; i++ ){
stack.pop();
}
stack.peek().next = stack.peek().next.next;
return sentinel.next;
}復雜度分析
時間復雜度：O(L)，其中 L是鏈表的長度，我們壓堆疊遍歷了一次鏈表，彈堆疊遍歷了N個節點，所以應該耗費O(L+N)時間，N <= L，所以時間復雜度依然是O(L)，而且我們可以看出，遍歷次數比兩次要少，但依然沒有達到“一次遍歷”的要求，
空間復雜度：O(L)，其中 L 是鏈表的長度，主要為堆疊的開銷，
6.3.5 方法三：雙指標（一次遍歷）
我們可以使用兩個指標 first 和 second 同時對鏈表進行遍歷，要求 first 比 second 超前 N 個節點，
這樣，它們總是保持著N的距離，當 first 遍歷到鏈表的末尾（null）時，second 就恰好處于第L-N+1，也就是倒數第 N 個節點了，
代碼如下：
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode sentinel = new ListNode(-1);
sentinel.next = head;
ListNode first = sentinel, second = sentinel;
for ( int i = 0; i < n + 1; i++ ){
first = first.next;
}
while ( first != null ){
first = first.next;
second = second.next;
}
second.next = second.next.next;
return sentinel.next;
}復雜度分析
時間復雜度：O(L)，其中 L是鏈表的長度，這次真正實作了一次遍歷，
空間復雜
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/300387.html
標籤：其他
上一篇：資深軟體測驗架構師10年測驗經驗結晶：《測驗架構師修煉之道：測驗工程師到測驗架構師》PDF高清版
下一篇：【計算機網路】實驗1：雙絞線制作