本文首發(fā)于我的個人博客：尾尾部落
鏈表是面試過程中經(jīng)常被問到的垒手，這里把劍指offer 和 LeetCode 中的相關題目做一個匯總，方便復習倒信。
1. 在 O(1) 時間刪除鏈表節(jié)點
題目描述：給定單向鏈表的頭指針和一個節(jié)點指針科贬，定義一個函數(shù)在O(1)時間刪除該節(jié)點。
解題思路：常規(guī)的做法是從鏈表的頭結點開始遍歷鳖悠，找到需要刪除的節(jié)點的前驅節(jié)點榜掌，把它的 next 指向要刪除節(jié)點的下一個節(jié)點，平均時間復雜度為O(n)乘综，不滿足題目要求憎账。
那是不是一定要得到被刪除的節(jié)點的前一個節(jié)點呢？其實不用的瘾带。我們可以很方面地得到要刪除節(jié)點的下一個節(jié)點鼠哥，如果我們把下一個節(jié)點的內(nèi)容復制到要刪除的節(jié)點上覆蓋原有的內(nèi)容熟菲，再把下一個節(jié)點刪除看政，那就相當于把當前要刪除的節(jié)點刪除了朴恳。舉個栗子，我們要刪除的節(jié)點i允蚣，先把i的下一個節(jié)點j的內(nèi)容復制到i于颖，然后把i的指針指向節(jié)點j的下一個節(jié)點。此時再刪除節(jié)點j嚷兔，其效果剛好是把節(jié)點i給刪除了森渐。
要注意兩種情況：
- 如果鏈表中只有一個節(jié)點，即頭節(jié)點等于要刪除的節(jié)點冒晰，此時我們在刪除節(jié)點之后同衣，還需要把鏈表的頭節(jié)點設置為NULL。
- 如果要刪除的節(jié)點位于鏈表的尾部壶运，那么它就沒有下一個節(jié)點耐齐，這時我們就要從鏈表的頭節(jié)點開始，順序遍歷得到該節(jié)點的前序節(jié)點蒋情，并完成刪除操作埠况。
參考代碼
public static ListNode deleteNode(ListNode head, ListNode toBeDeleted) {
// 如果輸入?yún)?shù)有空值就返回表頭結點
if (head == null || toBeDeleted == null) {
return head;
}
// 如果刪除的是頭結點，直接返回頭結點的下一個結點
if (head == toBeDeleted) {
return head.next;
}
// 下面的情況鏈表至少有兩個結點
// 在多個節(jié)點的情況下棵癣，如果刪除的是最后一個元素
if (toBeDeleted.next == null) {
// 找待刪除元素的前驅
ListNode tmp = head;
while (tmp.next != toBeDeleted) {
tmp = tmp.next;
}
// 刪除待結點
tmp.next = null;
}
// 在多個節(jié)點的情況下辕翰，如果刪除的是某個中間結點
else {
// 將下一個結點的值輸入當前待刪除的結點
toBeDeleted.value = toBeDeleted.next.value;
// 待刪除的結點的下一個指向原先待刪除引號的下下個結點，即將待刪除的下一個結點刪除
toBeDeleted.next = toBeDeleted.next.next;
}
// 返回刪除節(jié)點后的鏈表頭結點
return head;
}
2. 翻轉單鏈表
題目描述：輸出一個單鏈表的逆序反轉后的鏈表狈谊。
解題思路：用三個臨時指針 prev喜命、cur、next 在鏈表上循環(huán)一遍即可河劝。
3. 翻轉部分單鏈表：
題目描述：給定一個單向鏈表的頭結點head,以及兩個整數(shù)from和to,在單鏈表上把第from個節(jié)點和第to個節(jié)點這一部分進行反轉
舉例：1->2->3->4->5->null, from = 2, to = 4
結果：1->4->3->2->5->null
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null) return null;
if (head.next == null) return head;
int i = 1;
ListNode reversedNewHead = null;// 反轉部分鏈表反轉后的頭結點
ListNode reversedTail = null;// 反轉部分鏈表反轉后的尾結點
ListNode oldHead = head;// 原鏈表的頭結點
ListNode reversePreNode = null;// 反轉部分鏈表反轉前其頭結點的前一個結點
ListNode reverseNextNode = null;
while (head != null) {
if (i > n) {
break;
}
if (i == m - 1) {
reversePreNode = head;
}
if (i >= m && i <= n) {
if (i == m) {
reversedTail = head;
}
reverseNextNode = head.next;
head.next = reversedNewHead;
reversedNewHead = head;
head = reverseNextNode;
} else {
head = head.next;
}
i++;
}
reversedTail.next = reverseNextNode;
if (reversePreNode != null) {
reversePreNode.next = reversedNewHead;
return oldHead;
} else {
return reversedNewHead;
}
}
4. 旋轉單鏈表
題目描述：給定一個單鏈表渊抄，設計一個算法實現(xiàn)鏈表向右旋轉 K 個位置。
舉例： 給定 1->2->3->4->5->6->NULL, K=3
則4->5->6->1->2->3->NULL
解題思路：
- 方法一 雙指針丧裁，快指針先走k步护桦，然后兩個指針一起走，當快指針走到末尾時煎娇，慢指針的下一個位置是新的順序的頭結點二庵，這樣就可以旋轉鏈表了。
- 方法二 先遍歷整個鏈表獲得鏈表長度n缓呛，然后此時把鏈表頭和尾鏈接起來催享，在往后走n - k % n個節(jié)點就到達新鏈表的頭結點前一個點，這時斷開鏈表即可哟绊。
方法二代碼：
public class Solution { {
public ListNode rotateRight(ListNode head, int k) {
if (!head) return null;
int n = 1;
ListNode cur = head;
while (cur.next) {
++n;
cur = cur.next;
}
cur.next = head;
int m = n - k % n;
for (int i = 0; i < m; ++i) {
cur = cur.next;
}
ListNode newhead = cur.next;
cur.next = NULL;
return newhead;
}
};
5. 刪除單鏈表倒數(shù)第 n 個節(jié)點
題目描述：刪除單鏈表倒數(shù)第 n 個節(jié)點因妙，1 <= n <= length，盡量在一次遍歷中完成。
解題思路：雙指針法攀涵，找到倒數(shù)第 n+1 個節(jié)點铣耘，將它的 next 指向倒數(shù)第 n-1個節(jié)點。
6. 求單鏈表的中間節(jié)點
題目描述：求單鏈表的中間節(jié)點以故，如果鏈表的長度為偶數(shù)蜗细，返回中間兩個節(jié)點的任意一個，若為奇數(shù)怒详，則返回中間節(jié)點炉媒。
解題思路：快慢指針，慢的走一步昆烁，快的走兩步吊骤，當快指針到達尾節(jié)點時，慢指針移動到中間節(jié)點静尼。
// 遍歷一次白粉，找出單鏈表的中間節(jié)點
public ListNode findMiddleNode(ListNode head) {
if (null == head) {
return;
}
ListNode slow = head;
ListNode fast = head;
while (null != fast && null != fast.next) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
7. 鏈表劃分
題目描述： 給定一個單鏈表和數(shù)值x，劃分鏈表使得所有小于x的節(jié)點排在大于等于x的節(jié)點之前茅郎。
public class Solution {
/**
* @param head: The first node of linked list.
* @param x: an integer
* @return: a ListNode
*/
public ListNode partition(ListNode head, int x) {
// write your code here
if(head == null) return null;
ListNode leftDummy = new ListNode(0);
ListNode rightDummy = new ListNode(0);
ListNode left = leftDummy, right = rightDummy;
while (head != null) {
if (head.val < x) {
left.next = head;
left = head;
} else {
right.next = head;
right = head;
}
head = head.next;
}
right.next = null;
left.next = rightDummy.next;
return leftDummy.next;
}
}
8. 鏈表求和
題目描述：你有兩個用鏈表代表的整數(shù)蜗元，其中每個節(jié)點包含一個數(shù)字。數(shù)字存儲按照在原來整數(shù)中相反的順序系冗，使得第一個數(shù)字位于鏈表的開頭奕扣。寫出一個函數(shù)將兩個整數(shù)相加，用鏈表形式返回和掌敬。
解題思路：做個大循環(huán)惯豆，對每一位進行操作：
當前位：(A[i]+B[i])%10
進位：（A[i]+B[i]）/10
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode c1 = l1;
ListNode c2 = l2;
ListNode sentinel = new ListNode(0);
ListNode d = sentinel;
int sum = 0;
while (c1 != null || c2 != null) {
sum /= 10;
if (c1 != null) {
sum += c1.val;
c1 = c1.next;
}
if (c2 != null) {
sum += c2.val;
c2 = c2.next;
}
d.next = new ListNode(sum % 10);
d = d.next;
}
if (sum / 10 == 1)
d.next = new ListNode(1);
return sentinel.next;
}
}
9. 單鏈表排序
題目描述：在O(nlogn)時間內(nèi)對鏈表進行排序。
快速排序：
public ListNode sortList(ListNode head) {
//采用快速排序
quickSort(head, null);
return head;
}
public static void quickSort(ListNode head, ListNode end) {
if (head != end) {
ListNode node = partion(head, end);
quickSort(head, node);
quickSort(node.next, end);
}
}
public static ListNode partion(ListNode head, ListNode end) {
ListNode p1 = head, p2 = head.next;
//走到末尾才停
while (p2 != end) {
//大于key值時奔害，p1向前走一步楷兽，交換p1與p2的值
if (p2.val < head.val) {
p1 = p1.next;
int temp = p1.val;
p1.val = p2.val;
p2.val = temp;
}
p2 = p2.next;
}
//當有序時，不交換p1和key值
if (p1 != head) {
int temp = p1.val;
p1.val = head.val;
head.val = temp;
}
return p1;
}
歸并排序：
public ListNode sortList(ListNode head) {
//采用歸并排序
if (head == null || head.next == null) {
return head;
}
//獲取中間結點
ListNode mid = getMid(head);
ListNode right = mid.next;
mid.next = null;
//合并
return mergeSort(sortList(head), sortList(right));
}
/**
* 獲取鏈表的中間結點,偶數(shù)時取中間第一個
*
* @param head
* @return
*/
private ListNode getMid(ListNode head) {
if (head == null || head.next == null) {
return head;
}
//快慢指針
ListNode slow = head, quick = head;
//快2步华临，慢一步
while (quick.next != null && quick.next.next != null) {
slow = slow.next;
quick = quick.next.next;
}
return slow;
}
/**
*
* 歸并兩個有序的鏈表
*
* @param head1
* @param head2
* @return
*/
private ListNode mergeSort(ListNode head1, ListNode head2) {
ListNode p1 = head1, p2 = head2, head;
//得到頭節(jié)點的指向
if (head1.val < head2.val) {
head = head1;
p1 = p1.next;
} else {
head = head2;
p2 = p2.next;
}
ListNode p = head;
//比較鏈表中的值
while (p1 != null && p2 != null) {
if (p1.val <= p2.val) {
p.next = p1;
p1 = p1.next;
p = p.next;
} else {
p.next = p2;
p2 = p2.next;
p = p.next;
}
}
//第二條鏈表空了
if (p1 != null) {
p.next = p1;
}
//第一條鏈表空了
if (p2 != null) {
p.next = p2;
}
return head;
}
10. 合并兩個排序的鏈表
題目描述：輸入兩個單調(diào)遞增的鏈表芯杀，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則雅潭。
11. 復雜鏈表的復制
題目描述：輸入一個復雜鏈表（每個節(jié)點中有節(jié)點值揭厚，以及兩個指針，一個指向下一個節(jié)點扶供，另一個特殊指針指向任意一個節(jié)點）筛圆，返回結果為復制后復雜鏈表的head。（注意椿浓，輸出結果中請不要返回參數(shù)中的節(jié)點引用太援，否則判題程序會直接返回空）
12. 刪除鏈表中重復的結點
題目描述：在一個排序的鏈表中闽晦，存在重復的結點，請刪除該鏈表中重復的結點提岔，重復的結點不保留仙蛉，返回鏈表頭指針。 例如唧垦，鏈表1->2->3->3->4->4->5 處理后為 1->2->5
13. 判斷單鏈表是否存在環(huán)
題目描述：判斷一個單鏈表是否有環(huán)
分析：快慢指針捅儒，慢指針每次移動一步液样，快指針每次移動兩步振亮，如果存在環(huán)，那么兩個指針一定會在環(huán)內(nèi)相遇鞭莽。
14. 單鏈表是否有環(huán)擴展：找到環(huán)的入口點
題目描述：判斷單鏈表是否有環(huán)坊秸，如果有，找到環(huán)的入口點
解題思路：在第 5 題兩個指針相遇后澎怒，讓其中一個指針回到鏈表的頭部褒搔，另一個指針在原地，同時往前每次走一步喷面，當它們再次相遇時星瘾，就是在環(huán)路的入口點。
15. 判斷兩個無環(huán)單鏈表是否相交
題目描述：給出兩個無環(huán)單鏈表
解題思路：
- 方法一 最直接的方法是判斷 A 鏈表的每個節(jié)點是否在 B 鏈表中惧辈，但是這種方法的時間復雜度為 O(Length(A) * Length(B))琳状。
- 方法二 轉化為環(huán)的問題。把 B 鏈表接在 A 鏈表后面盒齿，如果得到的鏈表有環(huán)念逞，則說明兩個鏈表相交”呶蹋可以之前討論過的快慢指針來判斷是否有環(huán)翎承，但是這里還有更簡單的方法。如果 B 鏈表和 A 鏈表相交符匾，把 B 鏈表接在 A 鏈表后面時叨咖，B 鏈表的所有節(jié)點都在環(huán)內(nèi)，所以此時只需要遍歷 B 鏈表啊胶，看是否會回到起點就可以判斷是否相交甸各。這個方法需要先遍歷一次 A 鏈表，找到尾節(jié)點创淡，然后還要遍歷一次 B 鏈表痴晦，判斷是否形成環(huán)，時間復雜度為 O(Length(A) + Length(B))琳彩。
- 方法三 除了轉化為環(huán)的問題誊酌，還可以利用“如果兩個鏈表相交于某一節(jié)點部凑，那么之后的節(jié)點都是共有的”這個特點，如果兩個鏈表相交碧浊，那么最后一個節(jié)點一定是共有的涂邀。所以可以得出另外一種解法，先遍歷 A 鏈表箱锐，記住尾節(jié)點比勉，然后遍歷 B 鏈表，比較兩個鏈表的尾節(jié)點驹止，如果相同則相交浩聋，不同則不相交。時間復雜度為 O(Length(A) + Length(B))臊恋，空間復雜度為 O(1)衣洁，思路比解法 2 更簡單。
方法三的代碼：
public boolean isIntersect(ListNode headA, ListNode headB) {
if (null == headA || null == headB) {
return false;
}
if (headA == headB) {
return true;
}
while (null != headA.next) {
headA = headA.next;
}
while (null != headB.next) {
headB = headB.next;
}
return headA == headB;
}
16. 兩個鏈表相交擴展：求兩個無環(huán)單鏈表的第一個相交點
題目描述：找到兩個無環(huán)單鏈表第一個相交點抖仅，如果不相交返回空坊夫，要求在線性時間復雜度和常量空間復雜度內(nèi)完成。
解題思路：
- 方法一 如果兩個鏈表存在公共結點撤卢，那么它們從公共結點開始一直到鏈表的結尾都是一樣的环凿，因此我們只需要從鏈表的結尾開始，往前搜索放吩，找到最后一個相同的結點即可智听。但是題目給出的單向鏈表，我們只能從前向后搜索屎慢，這時瞭稼，我們就可以借助棧來完成。先把兩個鏈表依次裝到兩個棧中腻惠，然后比較兩個棧的棧頂結點是否相同环肘，如果相同則出棧，如果不同集灌，那最后相同的結點就是我們要的返回值悔雹。
- 方法二 先找出2個鏈表的長度，然后讓長的先走兩個鏈表的長度差欣喧，然后再一起走腌零，直到找到第一個公共結點。
- 方法三 由于2個鏈表都沒有環(huán)唆阿，我們可以把第二個鏈表接在第一個鏈表后面益涧，這樣就把問題轉化為求環(huán)的入口節(jié)點問題。
- 方法四 兩個指針p1和p2分別指向鏈表A和鏈表B驯鳖，它們同時向前走闲询，當走到尾節(jié)點時久免，轉向另一個鏈表，比如p1走到鏈表 A 的尾節(jié)點時扭弧，下一步就走到鏈表B阎姥，p2走到鏈表 B 的尾節(jié)點時，下一步就走到鏈表 A鸽捻，當p1==p2 時呼巴，就是鏈表的相交點
方法四的代碼：
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (null == headA || null == headB) {
return null;
}
if (headA == headB) {
return headA;
}
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != p2) {
// 遍歷完所在鏈表后從另外一個鏈表再開始
// 當 p1 和 p2 都換到另一個鏈表時，它們對齊了：
// （1）如果鏈表相交御蒲，p1 == p2 時為第一個相交點
// （2）如果鏈表不相交衣赶，p1 和 p2 同時移動到末尾，p1 = p2 = null删咱，然后退出循環(huán)
p1 = (null == p1) ? headB : p1.next;
p2 = (null == p2) ? headA : p2.next;
}
return p1;
}
17. 兩個鏈表相交擴展：判斷兩個有環(huán)單鏈表是否相交
題目描述：上面的問題是針對無環(huán)鏈表的屑埋，如果是鏈表有環(huán)呢豪筝？
解題思路：如果兩個有環(huán)單鏈表相交痰滋，那么它們一定共有一個環(huán)，即環(huán)上的任意一個節(jié)點都存在于兩個鏈表上续崖。因此可以先用之前快慢指針的方式找到兩個鏈表中位于環(huán)內(nèi)的兩個節(jié)點敲街，如果相交的話，兩個節(jié)點在一個環(huán)內(nèi)严望，那么移動其中一個節(jié)點多艇，在一次循環(huán)內(nèi)肯定可以與另外一個節(jié)點相遇。
