大廠算法面試之leetcode精講15.鏈表
視頻講解（高效學(xué)習(xí)）:點擊學(xué)習(xí)
目錄：
鏈表操作如下圖：
時間復(fù)雜度：
- prepend:
O(1) - append: 如果已知尾節(jié)點
O(1)宇挫，否則需要遍歷到尾節(jié)點察藐，然后加入新節(jié)點O(n) - insert: 插入到已知節(jié)點的后面
O(1)战得，需要先查找后插入O(n) - lookup:
O(n) - Delete：刪除已知節(jié)點
O(1)棘利，需要先查找后刪除O(n)
206. 反轉(zhuǎn)鏈表（easy）
方法1.頭插法：
- 思路：準(zhǔn)備一個臨時節(jié)點蚯姆，然后遍歷鏈表，準(zhǔn)備兩個指針head和next弟断，每次循環(huán)到一個節(jié)點的時候咏花，將
head.next指向temp.next，并且將temp.next指向head阀趴，head和next向后移一位迟螺。 - 復(fù)雜度分析：時間復(fù)雜度：
O(n)， n為鏈表節(jié)點數(shù)舍咖，空間復(fù)雜度：O(1)
js:
var reverseList = function (head) {
let temp = new ListNode();
let next = null;
while (head) {
next = head.next;//下一個節(jié)點
head.next = temp.next;
temp.next = head;//head接在temp的后面
head = next;//head向后移動一位
}
return temp.next;
};
方法2.迭代法：
- 思路: 遍歷鏈表，準(zhǔn)備prev排霉，curr窍株，next三個指針，在遍歷的過程中攻柠，讓當(dāng)前指針
curr.next指向前一個指針prev球订，然后不斷讓prev，curr瑰钮，next向后移動冒滩，直到curr為null - 復(fù)雜度分析：時間復(fù)雜度：
O(n)， n為鏈表節(jié)點數(shù)浪谴，空間復(fù)雜度：O(1)
js：
var reverseList = function (head) {
let prev = null;
let curr = head;
let next = null;
while (curr !== null) {
next = curr.next;//next向后移動一位
curr.next = prev;//讓當(dāng)前指針curr.next指向前一個指針prev
prev = curr;//prev向后移動一位
curr = next;//curr向后移動一位
//[curr.next, prev, curr] = [prev, curr, curr.next]
}
return prev;
};
java：
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
方法3.遞歸：
- 思路：用遞歸函數(shù)不斷傳入
head.next，直到head==null或者heade.next==null苟耻，到了遞歸最后一層的時候篇恒，讓后面一個節(jié)點指向前一個節(jié)點，然后讓前一個節(jié)點的next置為空凶杖，直到到達(dá)第一層胁艰，就是鏈表的第一個節(jié)點，每一層都返回最后一個節(jié)點。 - 復(fù)雜度分析：時間復(fù)雜度：
O(n)腾么，n是鏈表的長度奈梳。空間復(fù)雜度：O(n)解虱， n是遞歸的深度攘须，遞歸占用棧空間饭寺，可能會達(dá)到n層
js:
var reverseList = function(head) {
if (head == null || head.next == null) {//遞歸終止條件
return head;
}
const newHead = reverseList(head.next);//遞歸調(diào)用reverseList
head.next.next = head;//到了遞歸最后一層的時候阻课，讓后面一個節(jié)點指向前一個節(jié)點
head.next = null;//前一個節(jié)點的next置為空
return newHead;//返回最后一個節(jié)點
};
Java:
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
92. 反轉(zhuǎn)鏈表 II(medium)
方法1
- 思路：切斷l(xiāng)eft到right的子鏈艰匙，然后反轉(zhuǎn)，最后在反向連接
- 復(fù)雜度：時間復(fù)雜度
O(n)抹恳，空間復(fù)雜度O(1)
js：
var reverseBetween = function(head, left, right) {
const dummyNode = new ListNode(-1);
dummyNode.next = head;//虛擬頭節(jié)點
let pre = dummyNode;
for (let i = 0; i < left - 1; i++) {//pre遍歷到left的前一個節(jié)點
pre = pre.next;
}
let rightNode = pre;
for (let i = 0; i < right - left + 1; i++) {//rightNode遍歷到right的位置
rightNode = rightNode.next;
}
let leftNode = pre.next;//保存leftNode
let curr = rightNode.next;//保存rightNode.next
//切斷l(xiāng)eft到right的子鏈
pre.next = null;
rightNode.next = null;
//206題的邏輯 反轉(zhuǎn)left到right的子鏈
reverseLinkedList(leftNode);
//返鄉(xiāng)連接
pre.next = rightNode;
leftNode.next = curr;
return dummyNode.next;
};
const reverseLinkedList = (head) => {
let pre = null;
let cur = head;
while (cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}
java：
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode pre = dummyNode
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
ListNode rightNode = pre;
for (int i = 0; i < right - left + 1; i++) {
rightNode = rightNode.next;
}
ListNode leftNode = pre.next;
ListNode curr = rightNode.next;
pre.next = null;
rightNode.next = null;
reverseLinkedList(leftNode);
pre.next = rightNode;
leftNode.next = curr;
return dummyNode.next;
}
private void reverseLinkedList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}
}
方法2
- 思路：從left遍歷到right，在遍歷的過程中反轉(zhuǎn)鏈表
- 復(fù)雜度：時間復(fù)雜度
O(n)奋献，空間復(fù)雜度O(1)
js：
var reverseBetween = function(head, left, right) {
const dummy_node = new ListNode(-1);
dummy_node.next = head;//虛擬頭節(jié)點
let pre = dummy_node;
for (let i = 0; i < left - 1; ++i) {//pre前進(jìn)到left的前一個節(jié)點
pre = pre.next;
}
let cur = pre.next;
for (let i = 0; i < right - left; ++i) {//循環(huán)right - left次 反轉(zhuǎn)中間的節(jié)點
const next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummy_node.next;//返回虛擬頭節(jié)點的next
};
java：
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode pre = dummyNode;
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
ListNode cur = pre.next;
ListNode next;
for (int i = 0; i < right - left; i++) {
next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummyNode.next;
}
}
24. 兩兩交換鏈表中的節(jié)點 （medium）
方法1.遞歸：
ds_17
- 思路：用遞歸函數(shù)不斷傳入鏈表的下一個節(jié)點健霹，終止條件是
head === null|| head.next === null，也就是至少存在兩個節(jié)點進(jìn)行兩兩交換瓶蚂，在最后一層的時候開始兩兩反轉(zhuǎn)糖埋，讓當(dāng)前遞歸層的head.next指向交換后返回的頭節(jié)點，然后讓反轉(zhuǎn)后的新的頭節(jié)點指向當(dāng)前層的head的節(jié)點窃这，這樣就實現(xiàn)了兩兩交換瞳别，最后返回反轉(zhuǎn)后鏈表的頭節(jié)點 - 復(fù)雜的分析：時間復(fù)雜度
O(n)， n 是鏈表的節(jié)點數(shù)量杭攻∷盍玻空間復(fù)雜度O(n)，n是遞歸調(diào)用的椪捉猓空間
js:
var swapPairs = function(head) {
if (head === null|| head.next === null) {//終止條件馆铁，必須要有兩個節(jié)點
return head;
}
const newHead = head.next;//反轉(zhuǎn)后鏈表的頭節(jié)點，
head.next = swapPairs(newHead.next);//讓當(dāng)前遞歸層的head.next指向交換后返回的頭節(jié)點
newHead.next = head;//讓反轉(zhuǎn)后的新的頭節(jié)點指向當(dāng)前層的head的節(jié)點
return newHead;//返回反轉(zhuǎn)后的頭節(jié)點
};
Java:
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}
方法2.循環(huán)(虛擬頭節(jié)點)
ds_18
-
思路：設(shè)置虛擬頭節(jié)點dummyHead锅睛，讓
dummyHead.next指向head,當(dāng)temp.next !== null && temp.next.next !== null的時候埠巨，也就是dummyHead后面存在至少兩個節(jié)點，才開始兩兩交換節(jié)點现拒。交換之前準(zhǔn)備三個指針temp指向dummyHead乖订，node1是dummyHead后面的第一個節(jié)點，node2是dummyHead后的第二個節(jié)點具练，交換的時候讓temp.next指向node2乍构，node1.next指向node2.next，node2.next指向node1，每次循環(huán)迭代讓這三個節(jié)點后移一個節(jié)點哥遮，最后返回dummyHead.next岂丘，核心步驟是temp.next = node2; node1.next = node2.next; node2.next = node1; 復(fù)雜的分析：時間復(fù)雜度
O(n)， n 是鏈表的節(jié)點數(shù)量眠饮“铝保空間復(fù)雜度O(1)，
Js:
var swapPairs = function(head) {
const dummyHead = new ListNode(0);//虛擬頭節(jié)點
dummyHead.next = head;//初始的時候讓虛擬頭節(jié)點指向head仪召，
let temp = dummyHead;//temp指針
while (temp.next !== null && temp.next.next !== null) {//循環(huán)條件寨蹋，dummyHead后存在至少兩個節(jié)點
const node1 = temp.next;//node1指針，即dummyHead后的第一個節(jié)點
const node2 = temp.next.next;//node2指針扔茅，即dummyHead后的第二個節(jié)點
temp.next = node2;//下面三行是兩兩交換的核心代碼
node1.next = node2.next;
node2.next = node1;
temp = node1;//后移一個節(jié)點的位置
}
return dummyHead.next;//返回交換后的頭節(jié)點
};
Java:
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode temp = dummyHead;
while (temp.next != null && temp.next.next != null) {
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;
temp.next = node2;
node1.next = node2.next;
node2.next = node1;
temp = node1;
}
return dummyHead.next;
}
}
146. LRU 緩存機制 （medium）
ds_19
ds_212
-
思路：準(zhǔn)備一個哈希表和雙向鏈表存儲鍵值對已旧，哈希表O(1)就能查找到鍵值對，雙向鏈表方便從鏈表頭部新增節(jié)點召娜，也可以從隊尾刪除節(jié)點
- get的時候运褪，查找哈希表中有沒有該鍵值對，不存在就返回-1玖瘸，存在就返回該節(jié)點的值秸讹，并且將該節(jié)點移動到鏈表的頭部
- put的時候，查找哈希表中有沒有該鍵值對雅倒，如果存在就更新該節(jié)點璃诀，并且移動到鏈表的頭部，不存在就創(chuàng)建一個節(jié)點蔑匣，加入到哈希表和鏈表的頭部劣欢，并且讓節(jié)點數(shù)
count+1，如果超出容量殖演，就從隊尾刪除一個節(jié)點
復(fù)雜度：put氧秘、get時間復(fù)雜度都是
O(1)，空間復(fù)雜度O(c)趴久，c是LRU的容量
js:
class ListNode {
constructor(key, value) {//雙向鏈表的單個節(jié)點
this.key = key
this.value = value
this.next = null //指向后一個節(jié)點
this.prev = null //指向前一個節(jié)點
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity //容量
this.hashTable = {} //存放鍵值對信息
this.count = 0 //鍵值對數(shù)量
this.dummyHead = new ListNode() //dummy頭節(jié)點 方便在鏈表從開始的地方插入
this.dummyTail = new ListNode() //dummy尾節(jié)點 方便在鏈表從末尾刪除
this.dummyHead.next = this.dummyTail //dummyHead和dummyTail相互連接
this.dummyTail.prev = this.dummyHead
}
get(key) {
let node = this.hashTable[key]//查找哈希表中的鍵值對
if (node == null) return -1 //不存在該鍵值對 返回-1
this.moveToHead(node) //移動到鏈表頭
return node.value
}
put(key, value) {
let node = this.hashTable[key] //哈希表中查找該鍵值對
if (node == null) {
let newNode = new ListNode(key, value) //不存在就創(chuàng)建節(jié)點
this.hashTable[key] = newNode //加入哈希表
this.addToHead(newNode) //加入鏈表頭
this.count++ //節(jié)點數(shù)+1
if (this.count > this.capacity) { //超過容量 從隊尾刪除一個
this.removeLRUItem()
}
} else {
node.value = value //鍵值對存在于哈希表中 就更新
this.moveToHead(node) //移動到隊頭
}
}
moveToHead(node) {
this.removeFromList(node)//從鏈表中刪除節(jié)點
this.addToHead(node)//將該節(jié)點添加到鏈表頭
}
removeFromList(node) {//刪除的指針操作
let tempForPrev = node.prev
let tempForNext = node.next
tempForPrev.next = tempForNext
tempForNext.prev = tempForPrev
}
addToHead(node) {//加入鏈表頭的指針操作
node.prev = this.dummyHead
node.next = this.dummyHead.next
this.dummyHead.next.prev = node
this.dummyHead.next = node
}
removeLRUItem() {
let tail = this.popTail()//從鏈表中刪除
delete this.hashTable[tail.key]//從哈希表中刪除
this.count--
}
popTail() {
let tailItem = this.dummyTail.prev//通過dummyTail拿到最后一個節(jié)點 然后刪除
this.removeFromList(tailItem)
return tailItem
}
}
Java:
public class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {}
public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
}
private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
DLinkedNode newNode = new DLinkedNode(key, value);
cache.put(key, newNode);
addToHead(newNode);
++size;
if (size > capacity) {
DLinkedNode tail = removeTail();
cache.remove(tail.key);
--size;
}
}
else {
node.value = value;
moveToHead(node);
}
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
237. 刪除鏈表中的節(jié)點（easy）
ds_125
- 思路：將要刪除節(jié)點的下一個節(jié)點的值覆蓋自己的值丸相，然后讓當(dāng)前節(jié)點指向下一個節(jié)點的next
- 復(fù)雜度：時間復(fù)雜度和空間復(fù)雜度都是
O(1)
js：
var deleteNode = function(node) {
node.val = node.next.val//將要刪除節(jié)點的下一個節(jié)點的值覆蓋自己的值?
node.next = node.next.next//讓當(dāng)前節(jié)點指向下一個節(jié)點的next
};
java；
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
19. 刪除鏈表的倒數(shù)第 N 個結(jié)點 (medium)
方法1：棧
- 思路：循環(huán)鏈表彼棍，將所有的節(jié)點入棧灭忠，然后在彈出棧n次，就是我們需要刪除的節(jié)點
- 復(fù)雜度：時間復(fù)雜度
O(L)座硕，L是鏈表的長度弛作，空間復(fù)雜度O(L)。
方法2:遍歷2次
- 思路：遍歷一次鏈表的到鏈表的長度L华匾，在重頭遍歷到
L-n+1的位置就是需要刪除的節(jié)點映琳。 - 復(fù)雜度：時間復(fù)雜度
O(L)，L是鏈表的長度，空間復(fù)雜度O(1)
方法3:遍歷1次
- 思路：新建dummy節(jié)點指向head有鹿，指針n1，n2指向head谎脯，循環(huán)n2指針到n的位置葱跋，然后在同時移動n1，n2源梭，直到結(jié)尾娱俺，n1，n2的距離是n废麻，此時n1的位置就是需要刪除元素的位置
- 復(fù)雜度：時間復(fù)雜度
O(L)荠卷，L是鏈表的長度，空間復(fù)雜度O(1)
js:
var removeNthFromEnd = function (head, n) {
let dummy = new ListNode();
dummy.next = head;
let n1 = dummy;
let n2 = dummy;
for (let i = 0; i <= n; i++) {//n2移動n+1次
n2 = n2.next;
}
while (n2 !== null) {//同時移動n1脑溢，n2
n1 = n1.next;
n2 = n2.next;
}
n1.next = n1.next.next;//刪除元素
return dummy.next;
};
java:
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode n1 = dummy;
ListNode n2 = dummy;
for (int i = 0; i <= n; i++) {//n2移動n次
n2 = n2.next;
}
while (n2 != null) {//同時移動n1僵朗，n2
n1 = n1.next;
n2 = n2.next;
}
n1.next = n1.next.next;//刪除元素
return dummy.next;
}
}
203. 移除鏈表元素 (easy)
方法1.遞歸
- 思路：遞歸調(diào)用函數(shù)removeElements赖欣，傳入
head.next和 val屑彻，如果當(dāng)前元素值是val，則返回下一個元素顶吮，否則直接返回當(dāng)前元素 - 復(fù)雜度：時間復(fù)雜度
O(n)社牲，n是鏈表的長度，空間復(fù)雜度是O(n)悴了，遞歸棧的深度搏恤，最大為n
js：
//例：0->1->2->3 val=2
//level1: 0.next = removeElements(1, 2); return 1 0->1->3->null
//level2: 1.next = removeElements(2, 2); return 3 1->3->null
//level3: 2.next = removeElements(3, 2); return 3 2->3->null
//level4: 3.next = removeElements(null, 2); return null; 3->null
var removeElements = function(head, val) {
if (head === null) {//遞歸終止 遍歷完了鏈表
return head;
}
head.next = removeElements(head.next, val);//遞歸調(diào)用函數(shù)removeElements
return head.val === val ? head.next : head;//如果當(dāng)前元素值是val，則返回下一個元素湃交，否則直接返回當(dāng)前元素
};
java：
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return head;
}
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
}
方法2.迭代
- 思路：創(chuàng)建dummy節(jié)點熟空，將dummy節(jié)點的next指向head，temp指向dummy搞莺，當(dāng)temp的next不為null 不斷移動temp指針息罗，當(dāng)temp的next值是要刪除的 則刪除該節(jié)點
- 復(fù)雜度：時間復(fù)雜度
O(n)，n是鏈表的長度才沧，空間復(fù)雜度是O(1)
js：
//2->1->2->3
//dummy->2->1->2->3
var removeElements = function(head, val) {
const dummyHead = new ListNode(0);//創(chuàng)建dummy節(jié)點迈喉，將dummy節(jié)點的next指向head，temp指向dummy
dummyHead.next = head;
let temp = dummyHead;
while (temp.next !== null) {//當(dāng)temp的next不為null 不斷循環(huán)節(jié)點
if (temp.next.val == val) {
temp.next = temp.next.next;//當(dāng)temp的next值是要刪除的 則刪除該節(jié)點
} else {
temp = temp.next;//移動temp指針
}
}
return dummyHead.next;
};
java：
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode temp = dummyHead;
while (temp.next != null) {
if (temp.next.val == val) {
temp.next = temp.next.next;
} else {
temp = temp.next;
}
}
return dummyHead.next;
}
}
2. 兩數(shù)相加 （medium）
ds_166
- 思路：循環(huán)兩個鏈表温圆，計算每個節(jié)點相加的和在加進(jìn)位挨摸，然后計算進(jìn)位，處理最后一次的進(jìn)位岁歉。
- 復(fù)雜度：時間復(fù)雜度
O(max(m得运，n))，循環(huán)的次數(shù)是鏈表較長的那個∪鄄簦空間復(fù)雜度O(1)
js：
var addTwoNumbers = function(l1, l2) {
let head = null, tail = null;
let carry = 0;
while (l1 || l2) {//循環(huán)l1,l2鏈表
const n1 = l1 ? l1.val : 0;
const n2 = l2 ? l2.val : 0;
const sum = n1 + n2 + carry;//兩鏈表節(jié)點相加在加進(jìn)位
if (!head) {
head = tail = new ListNode(sum % 10);//當(dāng)沒有節(jié)點的時候新建節(jié)點
} else {
tail.next = new ListNode(sum % 10);//有節(jié)點的時候則加入tail節(jié)點的后面
tail = tail.next;
}
carry = Math.floor(sum / 10);//求進(jìn)位
if (l1) {//移動l1指針
l1 = l1.next;
}
if (l2) {//移動l2指針
l2 = l2.next;
}
}
if (carry > 0) {//最后一位節(jié)點是否有進(jìn)位
tail.next = new ListNode(carry);
}
return head;
};
java：
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int carry = 0;
while (l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
if (head == null) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = sum / 10;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}
}
21. 合并兩個有序鏈表 (easy)
方法1.遞歸
ds_167
- 思路：遞歸合并節(jié)點彬檀，當(dāng)前節(jié)點誰小，就讓這個較小的節(jié)點的next和另一個鏈表繼續(xù)遞歸合并瞬女，直到兩個鏈表有一個的nxet不存在了窍帝，那就沒法分割問題了，只能返回
- 復(fù)雜度：時間復(fù)雜度
O(m+n)诽偷，m坤学、n為兩個鏈表的長度，每次遞歸排除掉一個節(jié)點报慕，總遞歸次數(shù)是m+n深浮。空間復(fù)雜度O(m+n)眠冈，遞歸椃晌空間
js：
var mergeTwoLists = function(l1, l2) {
//遞歸終止 分隔到不能分割 也就是兩個鏈表有一個的nxet不存在了 那就沒法分割問題了 只能返回
if (l1 === null) {
return l2;
} else if (l2 === null) {
return l1;
} else if (l1.val < l2.val) {//當(dāng)前節(jié)點誰小，就讓這個較小的節(jié)點的next和另一個鏈表繼續(xù)遞歸合并
l1.next = mergeTwoLists(l1.next, l2);//分隔成合并l1.next, l2的子問題
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};
java：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
方法2.迭代
- 思路：設(shè)立虛擬頭節(jié)點prehead布卡，prev節(jié)點初始指向prehead，循環(huán)兩個鏈表雇盖，兩個鏈表中小的節(jié)點接在prev的后面忿等，不斷移動prev，最后返回
prehead.next - 復(fù)雜度：時間復(fù)雜度
O(m+n)崔挖，m贸街、n為兩個鏈表的長度，循環(huán)m+n次狸相⊙Ψ耍空間復(fù)雜度O(1)
js：
var mergeTwoLists = function(l1, l2) {
const prehead = new ListNode(-1);//虛擬頭節(jié)點
let prev = prehead;
while (l1 != null && l2 != null) {//循環(huán)兩個鏈表
if (l1.val <= l2.val) {//小的節(jié)點接在prev的后面
prev.next = l1;
l1 = l1.next;//向后移動l1
} else {
prev.next = l2;//向后移動l2
l2 = l2.next;
}
prev = prev.next;////向后移動prev
}
prev.next = l1 === null ? l2 : l1;//兩個鏈表一個遍歷完，另一個可能還沒遍歷完脓鹃，沒遍歷完的接上
return prehead.next;//返回prehead.next
};
java：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
}
83. 刪除排序鏈表中的重復(fù)元素 (easy)
時間復(fù)雜度：O(n)逸尖。空間復(fù)雜度O(1)
js:
var deleteDuplicates = function(head) {
let cur = head;
while(cur && cur.next) {
if(cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
};
java:
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while(cur != null && cur.next != null) {
if(cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}
328. 奇偶鏈表 (medium)
- 思路：奇偶指針循環(huán)鏈表冷溶，奇數(shù)指針不斷串連奇數(shù)節(jié)點，偶數(shù)指針不斷串連偶數(shù)節(jié)點尊浓，最后奇數(shù)指針的結(jié)尾連接偶數(shù)節(jié)點的開始
- 復(fù)雜度：時間復(fù)雜度
O(n)逞频，空間復(fù)雜度O(1)
js：
var oddEvenList = function(head) {
if (head === null) {
return head;
}
let evenHead = head.next;
let odd = head, even = evenHead;
while (even !== null && even.next !== null) {//偶數(shù)指針不為空 繼續(xù)循環(huán)
odd.next = even.next;//奇數(shù)指針指向偶數(shù)指針的next
odd = odd.next;//移動奇數(shù)指針
even.next = odd.next;//偶數(shù)指針指向奇數(shù)指針的next
even = even.next;//移動偶數(shù)指針
}
odd.next = evenHead;//奇數(shù)指針結(jié)尾連接上偶數(shù)指針的開始
return head;
};
java：
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return head;
}
ListNode evenHead = head.next;
ListNode odd = head, even = evenHead;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
