1. 兩數(shù)相加
題目描述
Leetcode:給定兩個非空鏈表來表示兩個非負整數(shù)。位數(shù)按照逆序方式存儲祭示，它們的每個節(jié)點只存儲單個數(shù)字肄满。將兩數(shù)相加返回一個新的鏈表。
你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)字都不會以零開頭稠歉。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
問題分析
Leetcode官方詳細解答地址：
https://leetcode-cn.com/problems/add-two-numbers/solution/
要對頭結(jié)點進行操作時掰担，考慮創(chuàng)建啞節(jié)點dummy，使用dummy->next表示真正的頭節(jié)點怒炸。這樣可以避免處理頭節(jié)點為空的邊界問題带饱。
我們使用變量來跟蹤進位，并從包含最低有效位的表頭開始模擬逐
位相加的過程阅羹。
Solution
我們首先從最低有效位也就是列表 l1和 l2 的表頭開始相加。注意需要考慮到進位的情況导梆！
/**
* 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 表示進位數(shù)
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;
//進位數(shù)
carry = sum / 10;
//新節(jié)點的數(shù)值為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. 翻轉(zhuǎn)鏈表
題目描述
劍指 offer:輸入一個鏈表轨淌，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素看尼。
問題分析
這道算法題猿诸，說直白點就是：如何讓后一個節(jié)點指向前一個節(jié)點！在下面的代碼中定義了一個 next 節(jié)點狡忙，該節(jié)點主要是保存要反轉(zhuǎn)到頭的那個節(jié)點，防止鏈表 “斷裂”址芯。
Solution
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
/**
*
* @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) {
// 保存要反轉(zhuǎn)到頭的那個節(jié)點
next = head.next;
// 要反轉(zhuǎn)的那個節(jié)點指向已經(jīng)反轉(zhuǎn)的上一個節(jié)點(備注:第一次反轉(zhuǎn)的時候會指向null)
head.next = pre;
// 上一個已經(jīng)反轉(zhuǎn)到頭部的節(jié)點
pre = head;
// 一直向鏈表尾走
head = next;
}
return pre;
}
}
測試方法：
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. 鏈表中倒數(shù)第k個節(jié)點
題目描述
劍指offer: 輸入一個鏈表灾茁，輸出該鏈表中倒數(shù)第k個結(jié)點。
問題分析
鏈表中倒數(shù)第k個節(jié)點也就是正數(shù)第(L-K+1)個節(jié)點谷炸，知道了只一點北专，這一題基本就沒問題！
首先兩個節(jié)點/指針旬陡，一個節(jié)點 node1 先開始跑拓颓，指針 node1 跑到 k-1 個節(jié)點后，另一個節(jié)點 node2 開始跑描孟，當 node1 跑到最后時驶睦，node2 所指的節(jié)點就是倒數(shù)第k個節(jié)點也就是正數(shù)第(L-K+1)個節(jié)點。
Solution
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
// 時間復(fù)雜度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;
}
// 聲明兩個指向頭結(jié)點的節(jié)點
ListNode node1 = head, node2 = head;
// 記錄節(jié)點的個數(shù)
int count = 0;
// 記錄k值匿醒，后面要使用
int index = k;
// p指針先跑场航，并且記錄節(jié)點數(shù)，當node1節(jié)點跑了k-1個節(jié)點后廉羔，node2節(jié)點開始跑溉痢，
// 當node1節(jié)點跑到最后時，node2節(jié)點所指的節(jié)點就是倒數(shù)第k個節(jié)點
while (node1 != null) {
node1 = node1.next;
count++;
if (k < 1) {
node2 = node2.next;
}
k--;
}
// 如果節(jié)點個數(shù)小于所求的倒數(shù)第k個節(jié)點，則返回空
if (count < index)
return null;
return node2;
}
}
4. 刪除鏈表的倒數(shù)第N個節(jié)點
Leetcode:給定一個鏈表孩饼，刪除鏈表的倒數(shù)第 n 個節(jié)點髓削，并且返回鏈表的頭結(jié)點。
示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當刪除了倒數(shù)第二個節(jié)點后镀娶，鏈表變?yōu)?1->2->3->5.
說明：
給定的 n 保證是有效的立膛。
進階：
你能嘗試使用一趟掃描實現(xiàn)嗎？
該題在 leetcode 上有詳細解答汽畴，具體可參考 Leetcode.
問題分析
我們注意到這個問題可以容易地簡化成另一個問題：刪除從列表開頭數(shù)起的第 (L - n + 1)個結(jié)點旧巾，其中 L是列表的長度。只要我們找到列表的長度 L忍些，這個問題就很容易解決鲁猩。
Solution
兩次遍歷法
首先我們將添加一個 啞結(jié)點 作為輔助，該結(jié)點位于列表頭部罢坝。啞結(jié)點用來簡化某些極端情況廓握，例如列表中只含有一個結(jié)點，或需要刪除列表的頭部嘁酿。在第一次遍歷中隙券，我們找出列表的長度 L。然后設(shè)置一個指向啞結(jié)點的指針闹司，并移動它遍歷列表娱仔，直至它到達第 (L - n) 個結(jié)點那里。我們把第 (L - n)個結(jié)點的 next 指針重新鏈接至第 (L - n + 2)個結(jié)點游桩，完成這個算法牲迫。
/**
* 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) {
// 啞結(jié)點，啞結(jié)點用來簡化某些極端情況借卧，例如列表中只含有一個結(jié)點盹憎，或需要刪除列表的頭部
ListNode dummy = new ListNode(0);
// 啞結(jié)點指向頭結(jié)點
dummy.next = head;
// 保存鏈表長度
int length = 0;
ListNode len = head;
while (len != null) {
length++;
len = len.next;
}
length = length - n;
ListNode target = dummy;
// 找到 L-n 位置的節(jié)點
while (length > 0) {
target = target.next;
length--;
}
// 把第 (L - n)個結(jié)點的 next 指針重新鏈接至第 (L - n + 2)個結(jié)點
target.next = target.next.next;
return dummy.next;
}
}
復(fù)雜度分析：
- 時間復(fù)雜度 O(L) ：該算法對列表進行了兩次遍歷，首先計算了列表的長度 LL 其次找到第 (L - n)(L?n) 個結(jié)點铐刘。 操作執(zhí)行了 2L-n2L?n 步陪每，時間復(fù)雜度為 O(L)O(L)。
- 空間復(fù)雜度 O(1) ：我們只用了常量級的額外空間镰吵。
進階——一次遍歷法：
**鏈表中倒數(shù)第N個節(jié)點也就是正數(shù)第(L-N+1)個節(jié)點檩禾。
其實這種方法就和我們上面第四題找“鏈表中倒數(shù)第k個節(jié)點”所用的思想是一樣的。基本思路就是： 定義兩個節(jié)點 node1疤祭、node2;node1 節(jié)點先跑锌订，node1節(jié)點 跑到第 n+1 個節(jié)點的時候,node2 節(jié)點開始跑.當node1 節(jié)點跑到最后一個節(jié)點時，node2 節(jié)點所在的位置就是第 （L-n ） 個節(jié)點（L代表總鏈表長度画株，也就是倒數(shù)第 n+1 個節(jié)點）
/**
* 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;
// 聲明兩個指向頭結(jié)點的節(jié)點
ListNode node1 = dummy, node2 = dummy;
// node1 節(jié)點先跑辆飘，node1節(jié)點 跑到第 n 個節(jié)點的時候,node2 節(jié)點開始跑
// 當node1 節(jié)點跑到最后一個節(jié)點時啦辐，node2 節(jié)點所在的位置就是第 （L-n ） 個節(jié)點，也就是倒數(shù)第 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:輸入兩個單調(diào)遞增的鏈表蜈项，輸出兩個鏈表合成后的鏈表芹关，當然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
問題分析
我們可以這樣分析:
- 假設(shè)我們有兩個鏈表 A,B紧卒；
- A的頭節(jié)點A1的值與B的頭結(jié)點B1的值比較侥衬，假設(shè)A1小，則A1為頭節(jié)點跑芳；
- A2再和B1比較轴总，假設(shè)B1小,則，A1指向B1博个；
- A2再和B2比較
就這樣循環(huán)往復(fù)就行了怀樟，應(yīng)該還算好理解。
考慮通過遞歸的方式實現(xiàn)盆佣！
Solution
遞歸版本：
/*
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;
}
}
}
