一、將兩個有序鏈表合并為一個新的有序鏈表并返回
方法一：迭代
首先懊渡，我們設(shè)定一個哨兵節(jié)點 "prehead" 刽射，這可以在最后讓我們比較容易地返回合并后的鏈表。我們維護(hù)一個 prev 指針剃执，我們需要做的是調(diào)整它的 next 指針誓禁。然后，我們重復(fù)以下過程肾档，直到 l1 或者 l2 指向了 null ：如果 l1 當(dāng)前位置的值小于等于 l2 摹恰，我們就把 l1 的值接在 prev 節(jié)點的后面同時將 l1 指針往后移一個。否則怒见，我們對 l2 做同樣的操作俗慈。不管我們將哪一個元素接在了后面，我們都把 prev 向后移一個元素遣耍。
在循環(huán)終止的時候闺阱， l1 和 l2 至多有一個是非空的。由于輸入的兩個鏈表都是有序的舵变，所以不管哪個鏈表是非空的酣溃，它包含的所有元素都比前面已經(jīng)合并鏈表中的所有元素都要大。這意味著我們只需要簡單地將非空鏈表接在合并鏈表的后面纪隙，并返回合并鏈表赊豌。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
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;
}
}
方法二：遞歸
- 終止條件：兩條鏈表分別名為 l1 和 l2，當(dāng) l1 為空或 l2 為空時結(jié)束
- 返回值：每一層調(diào)用都返回排序好的鏈表頭
- 本級遞歸內(nèi)容：如果 l1 的 val 值更小绵咱，則將 l1.next 與排序好的鏈表頭相接碘饼，l2 同理
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
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;
}
}
}
二、給定一個排序鏈表，刪除所有重復(fù)的元素派昧，使得每個元素只出現(xiàn)一次黔姜。
// 由于輸入的列表已排序，因此我們可以通過將結(jié)點的值與它之后的結(jié)點進(jìn)行比較來確定它是否為重復(fù)結(jié)點蒂萎。如果它是重復(fù)的秆吵，我們更改當(dāng)前結(jié)點的 next 指針，以便它跳過下一個結(jié)點并直接指向下一個結(jié)點之后的結(jié)點
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode current = head;
while(current != null && current.next != null) {
if(current.val == current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
}
三五慈、給定一個鏈表纳寂，判斷鏈表中是否有環(huán)。
方法一：哈希表
我們遍歷所有結(jié)點并在哈希表中存儲每個結(jié)點泻拦。如果當(dāng)前結(jié)點為空結(jié)點 null（即已檢測到鏈表尾部的下一個結(jié)點）毙芜，那么我們已經(jīng)遍歷完整個鏈表，并且該鏈表不是環(huán)形鏈表争拐。如果當(dāng)前結(jié)點的引用已經(jīng)存在于哈希表中腋粥，那么返回 true（即該鏈表為環(huán)形鏈表）
方法二：快慢指針
首先創(chuàng)建兩個不同速度的節(jié)點，如果兩個節(jié)點相同時架曹，則代表該鏈表是環(huán)形鏈表隘冲；
若不相同時，判斷快指針當(dāng)前節(jié)點/下一個節(jié)點是否到達(dá)終點(即null)绑雄，若為null則不是環(huán)形鏈表展辞，否則移動節(jié)點
class Solution {
public boolean hasCycle(ListNode head) {
/// 1、哈希表
// Set<ListNode> map = new HashSet<>();
// while(head != null) {
// if(map.contains(head)) {
// return true;
// } else {
// map.add(head);
// }
// head = head.next;
// }
// return false;
/// 2万牺、快慢指針
ListNode slow = head, fast = head.next;
while (slow != fast) {
if(fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
四罗珍、找到兩個單鏈表相交的起始節(jié)點。
方法一脚粟、暴力遍歷
對鏈表A中的每一個結(jié)點 a 覆旱，遍歷整個鏈表 B 并檢查鏈表 B 中是否存在結(jié)點和 a 相同。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/// 暴力遍歷
while(headA != null) {
ListNode temp = headB;
while(temp != null) {
if(headA == temp) {
return headA;
} else {
temp = temp.next;
}
}
headA = headA.next;
}
return headA;
}
}
方法二珊楼、哈希表
遍歷鏈表 A 并將每個結(jié)點存儲在哈希表中通殃。然后檢查鏈表 B 中的每一個結(jié)點 b 是否在哈希表中。若在厕宗，則 b為相交結(jié)點
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/// 哈希表
Set<ListNode> set = new HashSet<>();
while(headA != null || headA.next != null) {
if(headB == null || headB.next == null) return null;
if(set.contains(headB)) {
return headB;
} else {
set.add(headA);
}
headA = headA.next;
headB = headB.next;
}
return headA;
}
}
方法三、雙指針
- 創(chuàng)建兩個指針 pA 和 pB堕担，分別初始化為鏈表 A 和 B 的頭結(jié)點已慢。然后讓它們向后逐結(jié)點遍歷。
- 當(dāng) pA 到達(dá)鏈表的尾部時霹购，將它重定位到鏈表 B 的頭結(jié)點; 類似的佑惠，當(dāng) pB 到達(dá)鏈表的尾部時，將它重定位到鏈表 A 的頭結(jié)點。
- 若在某一時刻 pA 和 pB 相遇膜楷，則 pA/pB 為相交結(jié)點旭咽。
- 想弄清楚為什么這樣可行, 可以考慮以下兩個鏈表: A={1,3,5,7,9,11} 和 B={2,4,9,11}，相交于結(jié)點 9赌厅。 由于 B.length (=4) < A.length (=6)穷绵，pB 比 pA 少經(jīng)過 2 個結(jié)點，會先到達(dá)尾部特愿。將 pB 重定向到 A 的頭結(jié)點仲墨，pApA 重定向到 B 的頭結(jié)點后，pB 要比 pA 多走 2 個結(jié)點揍障。因此目养，它們會同時到達(dá)交點。
- 如果兩個鏈表存在相交毒嫡，它們末尾的結(jié)點必然相同癌蚁。因此當(dāng) pA/pB 到達(dá)鏈表結(jié)尾時，記錄下鏈表 A/B 對應(yīng)的元素兜畸。若最后元素不相同努释，則兩個鏈表不相交。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/// 雙指針
ListNode pA = headA, pB = headB;
while(pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
五膳叨、刪除鏈表中等于給定值 val 的所有節(jié)點洽洁。
示例:
輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5
這里需要注意的是：如果刪除的節(jié)點位于鏈表的頭部時 ，我們使用哨兵節(jié)點來解決該問題
- 初始化哨兵節(jié)點為 ListNode(0) 且設(shè)置 sentinel.next = head菲嘴。
- 初始化兩個指針 curr 和 prev 指向當(dāng)前節(jié)點和前繼節(jié)點饿自。
- 當(dāng) curr != null：
- 比較當(dāng)前節(jié)點和要刪除的節(jié)點：
- 若當(dāng)前節(jié)點就是要刪除的節(jié)點：則 prev.next = curr.next。
- 否則設(shè) prve = curr龄坪。
- 遍歷下一個元素：curr = curr.next昭雌。
- 返回 sentinel.next。
注：哨兵節(jié)點廣泛應(yīng)用于樹和鏈表中健田，如偽頭烛卧、偽尾、標(biāo)記等妓局，它們是純功能的总放，通常不保存任何數(shù)據(jù)，其主要目的是使鏈表標(biāo)準(zhǔn)化好爬，如使鏈表永不為空局雄、永不無頭、簡化插入和刪除存炮。
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode sentinel = new ListNode(0); // 哨兵節(jié)點炬搭，虛擬增加一個頭結(jié)點
sentinel.next = head;
ListNode prev = sentinel, curr = head;
while (curr != null) {
if (curr.val == val) {
prev.next = curr.next;
} else {
prev = curr;
}
curr = curr.next;
}
return sentinel.next;
}
}
六蜈漓、翻轉(zhuǎn)鏈表
class Solution {
public ListNode reverseList(ListNode head) {
// 1、 迭代
// ListNode preHead = null;
// ListNode prev = head;
// while(prev != null) {
// ListNode temp = prev.next;
// prev.next = preHead;
// preHead = prev;
// prev = temp;
// }
// return preHead;
/// 2宫盔、 遞歸
if (head == null || head.next == null) return head;
ListNode temp = reverseList(head.next);
head.next.next = head;
head.next = null;
return temp;
}
}
七融虽、請判斷一個鏈表是否為回文鏈表。
先翻轉(zhuǎn)鏈表 再比較
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head, prev = null, prepre = null;
while(fast != null && fast.next != null) {
/// 移動指針
prev = slow;
slow = slow.next;
fast = fast.next.next;
/// 翻轉(zhuǎn)前半部鏈表
prev.next = prepre;
prepre = prev;
}
if(fast != null) { slow = slow.next;} // 鏈表為奇數(shù)灼芭，需要去除中間節(jié)點
// 遍歷 對比
while (prev != null && slow != null) {
if (slow.val != prev.val) {
return false;
}
slow = slow.next;
prev = prev.next;
}
return true;
}
}
八有额、請編寫一個函數(shù)，使其可以刪除某個鏈表中給定的（非末尾）節(jié)點
從鏈表里刪除一個節(jié)點 node 的最常見方法是修改之前節(jié)點的 next 指針姿鸿，使其指向之后的節(jié)點谆吴。
在這里我們無法訪問我們想要刪除的節(jié)點 之前 的節(jié)點，我們始終不能修改該節(jié)點的 next 指針苛预。但是我們可以將想要刪除的節(jié)點的值替換為它后面節(jié)點中的值句狼，然后刪除它之后的節(jié)點。
因為我們知道要刪除的節(jié)點不是列表的末尾热某，所以我們可以保證這種方法是可行的腻菇。
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
九、給定一個帶有頭結(jié)點 head 的非空單鏈表昔馋，返回鏈表的中間結(jié)點筹吐。如果有兩個中間結(jié)點，則返回第二個中間結(jié)點秘遏。
使用雙指針丘薛，通過快慢指針找到中間點
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// fast != null && fast.next != null 用于找到第二個中間節(jié)點
// fast.next != null && fast.next.next != null 用于找到第一個中間節(jié)點
while( fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
十、給你一個單鏈表的引用結(jié)點 head邦危。鏈表中每個結(jié)點的值不是 0 就是 1洋侨。已知此鏈表是一個整數(shù)數(shù)字的二進(jìn)制表示形式。
請你返回該鏈表所表示數(shù)字的 十進(jìn)制值 倦蚪。
class Solution {
public int getDecimalValue(ListNode head) {
int sum = 0;
while (head != null) {
sum = sum * 2 + head.val;
head = head.next;
}
return sum;
}
}
注: 以上鏈表問題皆來源于https://leetcode-cn.com/problems/
