鏈表基礎(chǔ)
類別
1侣诵、合并兩個(gè)有序鏈表
2、合并 k 個(gè)有序鏈表
3边苹、尋找單鏈表的倒數(shù)第 k 個(gè)節(jié)點(diǎn)
4审丘、尋找單鏈表的中點(diǎn)
5、判斷單鏈表是否包含環(huán)并找出環(huán)起點(diǎn)
6勾给、判斷兩個(gè)單鏈表是否相交并找出交點(diǎn)
21. 合并兩個(gè)有序鏈表
題解：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
node = ListNode()
curr = node
while list1 and list2:
if list1.val < list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr = curr.next
if list1:
curr.next = list1
if list2:
curr.next = list2
return node.next
141. 環(huán)形鏈表
分析：
- 環(huán)形鏈表的存在必然會(huì)有快慢指針的未來(lái)相遇，循環(huán)終止條件即快指針先變成了None
題解：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
fast = head
slow = head
while fast:
if not fast.next:
return False
else:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
142. 環(huán)形鏈表 II
給定一個(gè)鏈表的頭節(jié)點(diǎn) head 锅知，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)播急。 如果鏈表無(wú)環(huán)，則返回 null售睹。
如果鏈表中有某個(gè)節(jié)點(diǎn)桩警，可以通過(guò)連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)昌妹。 為了表示給定鏈表中的環(huán)捶枢，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開(kāi)始）握截。如果 pos 是 -1，則在該鏈表中沒(méi)有環(huán)烂叔。注意：pos 不作為參數(shù)進(jìn)行傳遞谨胞，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。
不允許修改 鏈表蒜鸡。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個(gè)環(huán)胯努，其尾部連接到第二個(gè)節(jié)點(diǎn)。
示例 2：
輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個(gè)環(huán)逢防，其尾部連接到第一個(gè)節(jié)點(diǎn)叶沛。
示例 3：
輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒(méi)有環(huán)。
提示：
鏈表中節(jié)點(diǎn)的數(shù)目范圍在范圍 [0, 104] 內(nèi)
-10^5 <= Node.val <= 10^5
pos 的值為 -1 或者鏈表中的一個(gè)有效索引
分析：先判斷是否有環(huán)忘朝，再確定初始交點(diǎn)的位置
題解：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
break
if not fast or not fast.next:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
876. 鏈表的中間結(jié)點(diǎn)
給定一個(gè)頭結(jié)點(diǎn)為 head 的非空單鏈表灰署，返回鏈表的中間結(jié)點(diǎn)。
如果有兩個(gè)中間結(jié)點(diǎn)局嘁，則返回第二個(gè)中間結(jié)點(diǎn)溉箕。
示例 1：
輸入：[1,2,3,4,5]
輸出：此列表中的結(jié)點(diǎn) 3 (序列化形式：[3,4,5])
返回的結(jié)點(diǎn)值為 3 。 (測(cè)評(píng)系統(tǒng)對(duì)該結(jié)點(diǎn)序列化表述是 [3,4,5])导狡。
注意约巷，我們返回了一個(gè) ListNode 類型的對(duì)象 ans，這樣：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
輸入：[1,2,3,4,5,6]
輸出：此列表中的結(jié)點(diǎn) 4 (序列化形式：[4,5,6])
由于該列表有兩個(gè)中間結(jié)點(diǎn)旱捧，值分別為 3 和 4独郎，我們返回第二個(gè)結(jié)點(diǎn)。
提示：
給定鏈表的結(jié)點(diǎn)數(shù)介于 1 和 100 之間枚赡。
分析：
- 分奇偶來(lái)討論雙指針問(wèn)題
題解：
# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def middleNode(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
總結(jié)：對(duì)于鏈表成環(huán)或相似問(wèn)題氓癌，一般采用快指針和慢指針進(jìn)行分析解題
160. 相交鏈表
分析：本題的思路巧妙，將兩個(gè)鏈表分別連接到另一個(gè)鏈表后面贫橙，那么第一個(gè)相等的位置便是交點(diǎn)
題解：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
l1 = headA
l2 = headB
while l1 or l2:
if not l1: l1 = headB
if not l2: l2 = headA
if l1 == l2: return l1
l1 = l1.next
l2 = l2.next
遞歸反轉(zhuǎn)鏈表問(wèn)題
- 反轉(zhuǎn)鏈表
- 反轉(zhuǎn)鏈表前N的元素
- 反轉(zhuǎn)鏈表其中一部分
206. 反轉(zhuǎn)鏈表
分析：
- 對(duì)于鏈表反轉(zhuǎn)贪婉，分析一下需要肯定需要一個(gè)指針指向當(dāng)前node的前一個(gè)節(jié)點(diǎn)，一個(gè)用來(lái)指向當(dāng)前節(jié)點(diǎn)用來(lái)遍歷卢肃，由于鏈表是單向的疲迂，改變當(dāng)前節(jié)點(diǎn)的next指向會(huì)讓下一個(gè)節(jié)點(diǎn)丟失，因此需要再定義一個(gè)臨時(shí)變量莫湘，用來(lái)存儲(chǔ)當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)尤蒿。注意最后終止條件是cur指向None，此時(shí)pre便是新的鏈表的頭節(jié)點(diǎn)
題解：
- 方法一：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head:
return None
pre = None
cur = head
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
- 方法二：遞歸求解
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
last = self.reverseList(head.next)
head.next.next = head
head.next= None
return last
-
理解遞歸過(guò)程：
92. 反轉(zhuǎn)鏈表 II
給你單鏈表的頭指針 head 和兩個(gè)整數(shù) left 和 right 幅垮，其中 left <= right 腰池。請(qǐng)你反轉(zhuǎn)從位置 left 到位置 right 的鏈表節(jié)點(diǎn)，返回 反轉(zhuǎn)后的鏈表 。
示例 1：
輸入：head = [1,2,3,4,5], left = 2, right = 4
輸出：[1,4,3,2,5]
示例 2：
輸入：head = [5], left = 1, right = 1
輸出：[5]
提示：
鏈表中節(jié)點(diǎn)數(shù)目為 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
分析：
題解：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
if not head:
return head
dummy = ListNode()
pre = dummy
pre.next = head
for i in range(1, left):
pre = pre.next
cur = pre.next
for i in range(left, right):
future = cur.next
cur.next = future.next
future.next = pre.next
pre.next = future
return dummy.next
19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)
給你一個(gè)鏈表示弓，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)讳侨，并且返回鏈表的頭結(jié)點(diǎn)。
示例 1：
輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]
示例 2：
輸入：head = [1], n = 1
輸出：[]
示例 3：
輸入：head = [1,2], n = 1
輸出：[1]
提示：
鏈表中結(jié)點(diǎn)的數(shù)目為 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
分析：雙指針奏属，第一個(gè)指針先走n步跨跨，第二個(gè)再走，第一個(gè)到了拍皮，第二個(gè)便指向倒數(shù)第n個(gè)指針
題解：
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
if not head or not head.next:
return None
dummy = ListNode()
cur = dummy
fast = head
slow = head
cur.next = slow
for i in range(n):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
cur = cur.next
cur.next = slow.next
return dummy.next
25. K 個(gè)一組翻轉(zhuǎn)鏈表
給你一個(gè)鏈表歹叮，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)，請(qǐng)你返回翻轉(zhuǎn)后的鏈表铆帽。
k 是一個(gè)正整數(shù)咆耿，它的值小于或等于鏈表的長(zhǎng)度。
如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍爹橱，那么請(qǐng)將最后剩余的節(jié)點(diǎn)保持原有順序萨螺。
進(jìn)階：
你可以設(shè)計(jì)一個(gè)只使用常數(shù)額外空間的算法來(lái)解決此問(wèn)題嗎？
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值愧驱，而是需要實(shí)際進(jìn)行節(jié)點(diǎn)交換慰技。
示例 1：
輸入：head = [1,2,3,4,5], k = 2
輸出：[2,1,4,3,5]
示例 2：
輸入：head = [1,2,3,4,5], k = 3
輸出：[3,2,1,4,5]
示例 3：
輸入：head = [1,2,3,4,5], k = 1
輸出：[1,2,3,4,5]
示例 4：
輸入：head = [1], k = 1
輸出：[1]
提示：
列表中節(jié)點(diǎn)的數(shù)量在范圍 sz 內(nèi)
1 <= sz <= 5000
0 <= Node.val <= 1000
1 <= k <= sz
分析：
- 鏈表反轉(zhuǎn)通用方法：尾插法，效率較低组砚，但是很容易理解
- 我們用tail 移到要翻轉(zhuǎn)的部分最后一個(gè)元素
- 我們尾插法的意思就是,依次把cur移到tail后面吻商，循環(huán)執(zhí)行下去
題解：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
pre = dummy
tail = dummy
while True:
count = k
while count and tail:
count -= 1
tail = tail.next
if not tail: break
head = pre.next
while pre.next != tail:
cur = pre.next # 獲取下一個(gè)元素
# pre與cur.next連接起來(lái),此時(shí)cur(孤單)掉了出來(lái)
pre.next = cur.next
cur.next = tail.next # 和剩余的鏈表連接起來(lái)
tail.next = cur #插在tail后面
# 改變 pre tail 的值
pre = head
tail = head
return dummy.next
