<!-- MarkdownTOC --> - [1. 兩數相加](#1-兩數相加) - [題目描述](#題目描述) - [問題分析](#問題分析) - [Solution](#solution) - [2. 翻轉鏈表](#2-翻轉鏈表) - [題目描述](#題目描述-1) - [問題分析](#問題分析-1) - [Solution](#solution-1) - [3. 鏈表中倒數第k個節點](#3-鏈表中倒數第k個節點) - [題目描述](#題目描述-2) - [問題分析](#問題分析-2) - [Solution](#solution-2) - [4. 刪除鏈表的倒數第N個節點](#4-刪除鏈表的倒數第n個節點) - [問題分析](#問題分析-3) - [Solution](#solution-3) - [5. 合并兩個排序的鏈表](#5-合并兩個排序的鏈表) - [題目描述](#題目描述-3) - [問題分析](#問題分析-4) - [Solution](#solution-4) <!-- /MarkdownTOC --> # 1. 兩數相加 ### 題目描述 > Leetcode:給定兩個非空鏈表來表示兩個非負整數。位數按照逆序方式存儲，它們的每個節點只存儲單個數字。將兩數相加返回一個新的鏈表。 > >你可以假設除了數字 0 之外，這兩個數字都不會以零開頭。 示例： ``` 輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 輸出：7 -> 0 -> 8 原因：342 + 465 = 807 ``` ### 問題分析 Leetcode官方詳細解答地址： https://leetcode-cn.com/problems/add-two-numbers/solution/ > 要對頭結點進行操作時，考慮創建啞節點dummy，使用dummy->next表示真正的頭節點。這樣可以避免處理頭節點為空的邊界問題。 我們使用變量來跟蹤進位，并從包含最低有效位的表頭開始模擬逐 位相加的過程。  ### Solution **我們首先從最低有效位也就是列表 l1和 l2 的表頭開始相加。注意需要考慮到進位的情況！** ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ //https://leetcode-cn.com/problems/add-two-numbers/description/ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode p = l1, q = l2, curr = dummyHead; //carry 表示進位數 int carry = 0; while (p != null || q != null) { int x = (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0; int sum = carry + x + y; //進位數 carry = sum / 10; //新節點的數值為sum % 10 curr.next = new ListNode(sum % 10); curr = curr.next; if (p != null) p = p.next; if (q != null) q = q.next; } if (carry > 0) { curr.next = new ListNode(carry); } return dummyHead.next; } } ``` # 2. 翻轉鏈表 ### 題目描述 > 劍指 offer:輸入一個鏈表，反轉鏈表后，輸出鏈表的所有元素。  ### 問題分析 這道算法題，說直白點就是：如何讓后一個節點指向前一個節點！在下面的代碼中定義了一個 next 節點，該節點主要是保存要反轉到頭的那個節點，防止鏈表 “斷裂”。 ### Solution ```java public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } ``` ```java /** * * @author Snailclimb * @date 2018年9月19日 * @Description: TODO */ public class Solution { public ListNode ReverseList(ListNode head) { ListNode next = null; ListNode pre = null; while (head != null) { // 保存要反轉到頭的那個節點 next = head.next; // 要反轉的那個節點指向已經反轉的上一個節點(備注:第一次反轉的時候會指向null) head.next = pre; // 上一個已經反轉到頭部的節點 pre = head; // 一直向鏈表尾走 head = next; } return pre; } } ``` 測試方法： ```java public static void main(String[] args) { ListNode a = new ListNode(1); ListNode b = new ListNode(2); ListNode c = new ListNode(3); ListNode d = new ListNode(4); ListNode e = new ListNode(5); a.next = b; b.next = c; c.next = d; d.next = e; new Solution().ReverseList(a); while (e != null) { System.out.println(e.val); e = e.next; } } ``` 輸出： ``` 5 4 3 2 1 ``` # 3. 鏈表中倒數第k個節點 ### 題目描述 > 劍指offer: 輸入一個鏈表，輸出該鏈表中倒數第k個結點。 ### 問題分析 > **鏈表中倒數第k個節點也就是正數第(L-K+1)個節點，知道了只一點，這一題基本就沒問題！** 首先兩個節點/指針，一個節點 node1 先開始跑，指針 node1 跑到 k-1 個節點后，另一個節點 node2 開始跑，當 node1 跑到最后時，node2 所指的節點就是倒數第k個節點也就是正數第(L-K+1)個節點。  ### Solution ```java /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ // 時間復雜度O(n),一次遍歷即可 // https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking public class Solution { public ListNode FindKthToTail(ListNode head, int k) { // 如果鏈表為空或者k小于等于0 if (head == null || k <= 0) { return null; } // 聲明兩個指向頭結點的節點 ListNode node1 = head, node2 = head; // 記錄節點的個數 int count = 0; // 記錄k值，后面要使用 int index = k; // p指針先跑，并且記錄節點數，當node1節點跑了k-1個節點后，node2節點開始跑， // 當node1節點跑到最后時，node2節點所指的節點就是倒數第k個節點 while (node1 != null) { node1 = node1.next; count++; //node1跑了k-1個以后 node2才會從頭開始跑 if (k < 1) { node2 = node2.next; } k--; } // 如果節點個數小于所求的倒數第k個節點，則返回空 if (count < index) return null; return node2; } } ``` # 4. 刪除鏈表的倒數第N個節點 > Leetcode:給定一個鏈表，刪除鏈表的倒數第 n 個節點，并且返回鏈表的頭結點。 **示例：** ``` 給定一個鏈表: 1->2->3->4->5, 和 n = 2. 當刪除了倒數第二個節點后，鏈表變為 1->2->3->5. ``` **說明：** 給定的 n 保證是有效的。 **進階：** 你能嘗試使用一趟掃描實現嗎？ 該題在 leetcode 上有詳細解答，具體可參考 Leetcode. ### 問題分析 我們注意到這個問題可以容易地簡化成另一個問題：刪除從列表開頭數起的第 (L - n + 1)個結點，其中 L是列表的長度。只要我們找到列表的長度 L，這個問題就很容易解決。  ### Solution **兩次遍歷法** 首先我們將添加一個 **啞結點** 作為輔助，該結點位于列表頭部。啞結點用來簡化某些極端情況，例如列表中只含有一個結點，或需要刪除列表的頭部。在第一次遍歷中，我們找出列表的長度 L。然后設置一個指向啞結點的指針，并移動它遍歷列表，直至它到達第 (L - n) 個結點那里。**我們把第 (L - n)個結點的 next 指針重新鏈接至第 (L - n + 2)個結點，完成這個算法。** ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ // https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/description/ public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 啞結點，啞結點用來簡化某些極端情況，例如列表中只含有一個結點，或需要刪除列表的頭部 ListNode dummy = new ListNode(0); // 啞結點指向頭結點 dummy.next = head; // 保存鏈表長度 int length = 0; ListNode len = head; while (len != null) { length++; len = len.next; } length = length - n; ListNode target = dummy; // 找到 L-n 位置的節點 while (length > 0) { target = target.next; length--; } // 把第 (L - n)個結點的 next 指針重新鏈接至第 (L - n + 2)個結點 target.next = target.next.next; return dummy.next; } } ``` **復雜度分析：** - **時間復雜度 O(L)** ：該算法對列表進行了兩次遍歷，首先計算了列表的長度 LL 其次找到第 (L - n)(L?n) 個結點。 操作執行了 2L-n2L?n 步，時間復雜度為 O(L)O(L)。 - **空間復雜度 O(1)** ：我們只用了常量級的額外空間。 **進階——一次遍歷法：** > 鏈表中倒數第N個節點也就是正數第(L-N+1)個節點。 其實這種方法就和我們上面第四題找“鏈表中倒數第k個節點”所用的思想是一樣的。**基本思路就是：** 定義兩個節點 node1、node2;node1 節點先跑，node1節點 跑到第 n+1 個節點的時候,node2 節點開始跑.當node1 節點跑到最后一個節點時，node2 節點所在的位置就是第 （L-n ） 個節點（L代表總鏈表長度，也就是倒數第 n+1 個節點） ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; // 聲明兩個指向頭結點的節點 ListNode node1 = dummy, node2 = dummy; // node1 節點先跑，node1節點 跑到第 n 個節點的時候,node2 節點開始跑 // 當node1 節點跑到最后一個節點時，node2 節點所在的位置就是第 （L-n ） 個節點，也就是倒數第 n+1（L代表總鏈表長度） while (node1 != null) { node1 = node1.next; if (n < 1 && node1 != null) { node2 = node2.next; } n--; } node2.next = node2.next.next; return dummy.next; } } ``` # 5. 合并兩個排序的鏈表 ### 題目描述 > 劍指offer:輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。 ### 問題分析 我們可以這樣分析: 1. 假設我們有兩個鏈表 A,B； 2. A的頭節點A1的值與B的頭結點B1的值比較，假設A1小，則A1為頭節點； 3. A2再和B1比較，假設B1小,則，A1指向B1； 4. A2再和B2比較 就這樣循環往復就行了，應該還算好理解。 考慮通過遞歸的方式實現！ ### Solution **遞歸版本：** ```java /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ //https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1 == null){ return list2; } if(list2 == null){ return list1; } if(list1.val <= list2.val){ list1.next = Merge(list1.next, list2); return list1; }else{ list2.next = Merge(list1, list2.next); return list2; } } } ```