鏈表高頻面試題（包括反轉、合併、相交、分割、環長等）
- 整個鏈表翻轉
https://leetcode-cn.com/problems/reverse-linked-list/
1.1 題目描述
反轉一個單鏈表。
示例:
-
輸入: 1->2->3->4->5->NULL
-
輸出: 5->4->3->2->1->NULL
進階: 你可以迭代或遞歸地反轉鏈表。你能否用兩種方法解決這道題？
1.2 算法實現
1.2.1 算法思路
雙指針：一個指針 pre 指向原鏈表當前節點的前一個節點，另一個指針 next 暫存當前節點的下一個節點。
依次遍歷鏈表的各個節點，每遍歷一個節點即將其指向前一個節點（倒置），主要分 4 步：
-
先備份後一個節點（以防移動指針的時候找不到下一個節點）：next = head.Next；
-
後一個節點的 Next 指向前一個節點：next.Next = pre；
-
前置節點後移一個位置到當前節點：pre = head;
-
後置節點後移一個位置到下一個節點：head = next，注意這一步（千萬不要）容易忽略。
1.2.2 代碼實現
type LikedList struct{
Val int
Next *LikedList
}
// 頭插法，倒置單鏈表
func reverseLikedList(head *LikedList)*LikedList{
if(head == nil || head.Next == nil){
return head
}
var pre, next *LikedList
// head是當前節點，pre是當前節點的前一個幾點，next是當前節點的後一個節點
for head != nil { // 當前節點不爲空
next = head.Next // 備份head.Next（指向當前節點的下一個節點），防止移動節點時找不到後置節點
head.Next = pre // 更新head.Next，後一個節點指向前一個（翻轉）
pre = head // 前一個節點後移
head = next // 當前節點後移
}
return pre // 注意：當pre指向原鏈表的最後一個節點時，head已經指向最後一個節點的Next即空節點，所以這裏應返回pre
}- 反轉鏈表中的第 m 至第 n 個節點
題目來源：
https://leetcode-cn.com/problems/reverse-linked-list-ii
2.1 題目描述
反轉從位置 m 到 n 的鏈表。請使用一趟掃描完成反轉。
說明:
1 ≤ m ≤ n ≤ 鏈表長度。
示例:
-
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
-
輸出: 1->4->3->2->5->NULL
2.2 算法實現
2.2.1 算法思路
有四個關鍵的位置需要記錄：第 m 個節點及其前驅節點、第 n 個節點及其後繼節點。
-
對整個鏈表遍歷，將鏈表 head 的頭指針向後移動 m-1 個節點，即爲第 m 個節點，記其前驅節點爲 pre；
-
自第 m 個節點開始逆置 changLen = n-m+1 個節點，即將第 m 至第 n 個節點依次反轉，並記錄下來反轉後的頭結點 reversedListHead 和尾節點 reversedListTail；
-
將反轉後的尾節點 reversedListTail 的 Next 域與第 n 個節點的後繼節點 head 連接，pre 節點的 Next 域與 reversedListHead 連接。
2.2.2 代碼實現
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, m int, n int) *ListNode {
changeLen := n - m + 1 // 計算需要逆置的節點個數
var pre *ListNode = nil // 初始化開始逆置的節點的前驅
var result *ListNode = head // 最終轉換後的鏈表的頭結點，非特殊情況即爲head
move := m - 1 // head向後移動m-1個位置指向第m個節點
for(head != nil && move > 0){ // 將head後移m-1個位置，即
pre = head // for循環後pre指向第m個節點的前驅節點
head = head.Next // for循環後head指向第m個節點
move--
}
var reversedListTail *ListNode = head // 此時reversedListTail指向的是第m個節點，該節點即是鏈表片段反轉後的尾節點
var reversedListHead *ListNode = nil // 記錄鏈表片段反轉後的頭結點
for(head != nil && changeLen > 0){ // 逆置changeLen個節點
next := head.Next // 暫存當前節點的下一個節點
head.Next = reversedListHead // 當前節點的Next指針域指向新開闢的反轉後的頭結點
reversedListHead = head // 反轉後的鏈表的頭結點後移一個位置
head = next // 當前節點後移一個節點
changeLen-- // 每完成一個節點逆置，changLen--
}
reversedListTail.Next = head // 連接逆置後的鏈表尾與逆置段的後一個節點，翻轉後的尾節點指向第n個節點的下一個節點
if(pre != nil){ // 如果pre不爲空，說明不是從第1個節點開始逆置的，即m > 1
pre.Next = reversedListHead // 將逆置鏈表開始的節點前驅與逆置後的頭結點連接起來
}else{ // 如果pre爲空，說明m=1，即從第1個節點開始逆置，結果即爲逆置後的頭結點
result = reversedListHead
}
return result
}- 求兩個鏈表之間的交點
3.1 題目描述
題目來源：
https://leetcode-cn.com/problems/intersection-of-two-linked-lists
編寫一個程序，找到兩個單鏈表相交的起始節點。
如下面的兩個鏈表：
在節點 c1 開始相交。
示例 1：
-
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
-
輸出：Reference of the node with value = 8
輸入解釋：相交節點的值爲 8 （注意，如果兩個列表相交則不能爲 0）。從各自的表頭開始算起，鏈表 A 爲 [4,1,8,4,5]，鏈表 B 爲 [5,0,1,8,4,5]。在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點。
推薦：250 期面試題彙總
示例 2：
-
輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
-
輸出：Reference of the node with value = 2
輸入解釋：相交節點的值爲 2 （注意，如果兩個列表相交則不能爲 0）。從各自的表頭開始算起，鏈表 A 爲 [0,9,1,2,4]，鏈表 B 爲 [3,2,4]。在 A 中，相交節點前有 3 個節點；在 B 中，相交節點前有 1 個節點。
示例 3：
-
輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
-
輸出：null
輸入解釋：從各自的表頭開始算起，鏈表 A 爲 [2,6,4]，鏈表 B 爲 [1,5]。由於這兩個鏈表不相交，所以 intersectVal 必須爲 0，而 skipA 和 skipB 可以是任意值。解釋：這兩個鏈表不相交，因此返回 null。
注意：
-
如果兩個鏈表沒有交點，返回 null.
-
在返回結果後，兩個鏈表仍須保持原有的結構。
-
可假定整個鏈表結構中沒有循環。
-
程序儘量滿足 O(n) 時間複雜度，且僅用 O(1) 內存。
3.2 算法實現
3.2.1 算法思路
-
對兩個鏈表 ListNode1 和 ListNode2 分別遍歷，計算出其長度 len1 和 len2；
-
長鏈表的頭指針後移 abs(len1 - len2) 個節點；
-
當鏈表未遍歷到頭，兩鏈表指向同一個節點時，該節點即爲兩鏈表的交點，沒有指向同一個節點則兩個頭結點指針繼續後移；遍歷完還沒有找到，則說明沒有交點，返回 nil。
3.2.2 代碼實現
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
var lenA, lenB int // 分別記錄鏈表headA和鏈表headB的長度
lenA = getListLength(headA)
lenB = getListLength(headB)
if lenA > lenB {
headA = forwardDeltaLenNode(lenA, lenB, headA) // headA鏈表的頭結點指向移動多出的節點個位置後
}else{
headB = forwardDeltaLenNode(lenB, lenA, headB) // 如果鏈表headB長，移動其頭結點到相應位置
}
for headA != nil && headB != nil { // 沒有到達鏈表末尾
if(headA == headB){ // 當前兩個鏈表的節點相同，即指向同一個節點，說明找到的交點；否則，兩鏈表同時後移
return headA
}
headA = headA.Next
headB = headB.Next
}
return nil // 遍歷到鏈表末尾還沒有找到同一個節點，說明兩鏈表沒有交點
}
// 逐個節點遍歷，獲取鏈表長度
func getListLength(head *ListNode)int{
var lengthList int
for head != nil {
lengthList++
head = head.Next
}
return lengthList
}
// 較長鏈表移動 長鏈表長度-短鏈表長度 個節點後對應的頭指針
// 參數longLen和shortLen分別表示長鏈表和短鏈表的長度，longList對應長鏈表
func forwardDeltaLenNode(longLen, shortLen int, longList *ListNode)*ListNode{
deltaLen := longLen - shortLen
for longList != nil && deltaLen != 0{
longList = longList.Next
deltaLen--
}
return longList // 如果longList爲nil或者deltaLen=0直接返回此時的頭結點longList
}- 判斷鏈表是否有環；如果有環，給出環所在的起始節點及環的長度。
4.1 判斷鏈表是否有環
4.2 給出有環鏈表的環的起始節點及長度
- 將鏈表換分爲以某個值 x 爲界限的前後兩部分
鏈表劃分依據：鏈表前面的部門小於 x，後面部分大於等於 x，且原有節點的相對順序不變。如：將 1->3-7->2->5->3->6-9-2 劃分爲以 5 爲界限的前後兩部分：1->3->2->3->2 ->7->5->6->9
5.1 問題描述
給定一個鏈表和一個特定值 x，對鏈表進行分隔，使得所有小於 x 的節點都在大於或等於 x 的節點之前。
你應當保留兩個分區中每個節點的初始相對位置。
示例:
-
輸入: head = 1->4->3->2->5->2, x = 3
-
輸出: 1->2->2->4->3->5
鏈接：
https://leetcode-cn.com/problems/partition-list
5.2 算法實現
5.2.1 算法思路
鏈表分爲前後兩個部分，可以先依次遍歷鏈表，將小於 x 的節點依次插入到 preHead 指向的前半部分鏈表後面，將大於等於 x 的節點連接到 postHead 對應的另一個鏈表中；鏈表遍歷完將 preHead 的尾節點的 Next 域指向 postHead 結點的下一個節點，postHead 的尾節點的 Next 域置爲空，即實現了前後兩個鏈表的連接。
爲了連接 preHead 和 postHead 兩個鏈表，需要分別知道兩個鏈表的尾部，這裏使用 prePtr 和 postPtr 指針分別對 preHead 和 postHead 進行遍歷，知道兩個鏈表的尾節點。
-
前一個鏈表：preHead->1->2->2
-
後一個鏈表：postHead->4->3->5
5.2.2 代碼實現
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func partition(head *ListNode, x int) *ListNode {
//var preHead, postHead *ListNode // 前後兩部分鏈表的頭結點，不能這麼聲明，這樣聲明的話兩者都爲&ListNode{0, nil}其中Next域爲nil，當運行到prePtr.Next = head時會報panic: runtime error:invalid memory address or nil pointer deference錯誤
preHead := &ListNode{0, nil} // 生成一個preHead鏈表的頭結點，該節點固定一直不對其移動，改頭節點的Val爲多少都不影響結果，因爲使用的是頭結點的Next節點
postHead := &ListNode{0, nil} // 生成一個postHead鏈表的頭結點，該節點固定不動
prePtr := preHead // prePtr指針對preHead鏈表進行遍歷，注意：開始時其指向preHead
postPtr := postHead
for head != nil { // 遍歷原鏈表
if(head.Val < x ){ // 小於x的節點尾插到preHead鏈表後面
prePtr.Next = head // prePtr的Next域指向當前節點，即將當前節點從preHead鏈表尾部prePtr依次插入
prePtr = head // prePtr指針後移一位，指向當前節點
}else{ // 大於等於x的節點放在postHead鏈表的後面
postPtr.Next = head // 將當前節點插入到postHead鏈表尾節點postPtr後面
postPtr = head // postHead鏈表的尾節點後移一位
}
head = head.Next // 當前指針後移一位
}
// 對head鏈表遍歷結束分爲preHead和postHead兩個子鏈表
prePtr.Next = postHead.Next // 注意：這裏是將preHead鏈表的尾節點prePtr的Next域指向postHead鏈表頭結點的下一個節點
postPtr.Next = nil // postPtr的尾節點的Next域指向空
return preHead.Next // 返回preHead鏈表的Next之後的鏈表
}來源：gonline.blog.csdn.net/article/details/104187852
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/tfHv11RNwjHDlqAsjGeD9w