我經(jīng)常搞混的點(diǎn)：
1. first = first.next表示的是移動(dòng)first指針的位置。
如果寫first.next = first.next.next，則表示的是更改鏈表結(jié)構(gòu)，這會跳過first指針的下一個(gè)節(jié)點(diǎn)，改變鏈表本身的結(jié)構(gòu)。
因此我區(qū)分清楚：僅僅需要移動(dòng)first指針的位置，需要更改鏈表的結(jié)構(gòu)。
2.?while first:和while first.next:都是判斷條件，兩者有不同的含義。
while first:：判斷的是first指針是否存在。只要first指針指向的節(jié)點(diǎn)（包括最后的None）存在，循環(huán)就會繼續(xù)。
while first.next:：判斷的是first指針的下一個(gè)節(jié)點(diǎn)是否存在。只有當(dāng)first指針的下一個(gè)節(jié)點(diǎn)存在，循環(huán)才會繼續(xù)。
???????24. 兩兩交換鏈表中的節(jié)點(diǎn)
給你一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后鏈表的頭節(jié)點(diǎn)。你必須在不修改節(jié)點(diǎn)內(nèi)部的值的情況下完成本題（即，只能進(jìn)行節(jié)點(diǎn)交換）。
示例 1：
輸入：head = [1,2,3,4]
輸出：[2,1,4,3]
示例 2：輸入：head = []
輸出：[]
示例 3：輸入：head = [1]
輸出：[1]
?提示：
鏈表中節(jié)點(diǎn)的數(shù)目在范圍 [0, 100] 內(nèi)
0 <= Node.val <= 100
奇數(shù)節(jié)點(diǎn)最后一個(gè)節(jié)點(diǎn)無法兩兩配對，因此最后一個(gè)節(jié)點(diǎn)不做交換。
偶數(shù)節(jié)點(diǎn)兩兩進(jìn)行交換。
仍然使用虛擬頭節(jié)點(diǎn)的方法。定義一個(gè)dummy節(jié)點(diǎn)指向head，除此之外定義一個(gè)curr臨時(shí)指針用于遍歷整個(gè)鏈表。
重點(diǎn)：當(dāng)前節(jié)點(diǎn)n對應(yīng)的應(yīng)該是curr.next, n節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為curr, n節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為curr.next.next。
# 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 swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
time: O(n)
space: O(1)
"""
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next is not None and curr.next.next is not None:
temp1 = curr.next # node1 temp
temp2 = curr.next.next # node2 temp
temp3 = curr.next.next.next # node3 temp
curr.next = temp2 # curr points to 2
temp2.next = temp1 # 2 points to 1
temp1.next = temp3 # 1 points to 3
curr = curr.next.next # move curr to the node before next pair
return dummy.next # dummy.next指向的是新鏈表的頭節(jié)點(diǎn)?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
?進(jìn)階：你能嘗試使用一趟掃描實(shí)現(xiàn)嗎？
這道題的難點(diǎn)是找到倒數(shù)第n個(gè)節(jié)點(diǎn)，讓后才能刪除。
這道題需要用雙指針的思路，定義一個(gè)快指針，再定義一個(gè)慢指針，先讓快指針走n個(gè)節(jié)點(diǎn)，再讓兩個(gè)指針同時(shí)前進(jìn)，直到快指針移動(dòng)到null值，這個(gè)時(shí)候慢指針對應(yīng)的就是將要移除的倒數(shù)第n個(gè)節(jié)點(diǎn)。
首先，初始化兩個(gè)指針，一開始都指向頭結(jié)點(diǎn)。然后，讓第一個(gè)指針向前移動(dòng)n個(gè)節(jié)點(diǎn)，然后兩個(gè)指針同時(shí)向前移動(dòng)，直到第一個(gè)指針到達(dá)末尾。此時(shí)，第二個(gè)指針?biāo)诘奈恢镁褪堑箶?shù)第n個(gè)節(jié)點(diǎn)。在實(shí)現(xiàn)過程中，為了方便處理邊界條件（例如刪除的節(jié)點(diǎn)是頭結(jié)點(diǎn)），通常會使用一個(gè)虛擬頭結(jié)點(diǎn)。
為什么這道題可以聯(lián)想到雙指針解法？雙指針法在解決鏈表問題上非常常見，尤其是涉及鏈表中相對位置或者需要遍歷鏈表找到特定元素的情況。?當(dāng)你需要在鏈表中找到某種相對位置（如中點(diǎn)，倒數(shù)第N個(gè)節(jié)點(diǎn)等）時(shí)，你可以嘗試使用雙指針法。在這個(gè)具體問題中，我們知道我們需要找到倒數(shù)第n個(gè)節(jié)點(diǎn)，這就是一個(gè)明顯的相對位置問題，因此雙指針法成為一個(gè)可能的解決方案。
這里比較需要重視的一點(diǎn)是，先讓快指針走n個(gè)節(jié)點(diǎn)，再讓兩個(gè)指針同時(shí)前進(jìn)，直到快指針移動(dòng)到null值，這個(gè)時(shí)候慢指針對應(yīng)的就是將要移除的倒數(shù)第n個(gè)節(jié)點(diǎn)。但是我們要?jiǎng)h除倒數(shù)第n個(gè)節(jié)點(diǎn)，需要獲取的是第n個(gè)節(jié)點(diǎn)的前一位置的curr，因此我們可以讓快指針走n+1步。
# 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 removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
time: O(n) 只遍歷了一次鏈表。
space: O(1) 我們只使用了兩個(gè)指針fast和slow，和一個(gè)虛擬節(jié)點(diǎn) dummy，它們都是常數(shù)級別的空間
"""
# 創(chuàng)建一個(gè)虛擬節(jié)點(diǎn)，并將其下一個(gè)指針設(shè)置為鏈表的頭部
dummy = ListNode(0)
dummy.next = head
# 創(chuàng)建兩個(gè)指針，慢指針和快指針，并將它們初始化為虛擬節(jié)點(diǎn)
fast = dummy
slow = dummy
# 快指針比慢指針快 n+1 步
for i in range(n+1):
fast = fast.next
# 移動(dòng)兩個(gè)指針，直到快速指針到達(dá)鏈表的末尾
while fast:
fast = fast.next
slow = slow.next
# 通過更新第 (n-1) 個(gè)節(jié)點(diǎn)的 next 指針刪除第 n 個(gè)節(jié)點(diǎn)
slow.next = slow.next.next
return dummy.next
面試題 02.07. 鏈表相交
給你兩個(gè)單鏈表的頭節(jié)點(diǎn)?headA 和 headB ，請你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表沒有交點(diǎn)，返回 null 。
圖示兩個(gè)鏈表在節(jié)點(diǎn) c1 開始相交：
題目數(shù)據(jù) 保證 整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。
注意，函數(shù)返回結(jié)果后，鏈表必須 保持其原始結(jié)構(gòu) 。
示例 1：
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節(jié)點(diǎn)的值為 8 （注意，如果兩個(gè)鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。
在 A 中，相交節(jié)點(diǎn)前有 2 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)。
示例?2：
輸入：intersectVal?= 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2'
解釋：相交節(jié)點(diǎn)的值為 2 （注意，如果兩個(gè)鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]。
在 A 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 1 個(gè)節(jié)點(diǎn)。
示例?3：
輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
由于這兩個(gè)鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個(gè)鏈表不相交，因此返回 null 。
?提示：
listA 中節(jié)點(diǎn)數(shù)目為 m
listB 中節(jié)點(diǎn)數(shù)目為 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 沒有交點(diǎn)，intersectVal 為 0
如果 listA 和 listB 有交點(diǎn)，intersectVal == listA[skipA + 1] == listB[skipB + 1]
?進(jìn)階：你能否設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度 O(n) 、僅用 O(1) 內(nèi)存的解決方案？
這道題需要注意的是：數(shù)值相同，不代表指針相同。
這道題目，不僅考察對鏈表的操作，而且還需要一些數(shù)學(xué)運(yùn)算。
主要考察兩知識點(diǎn)：
- 判斷鏈表是否環(huán)
- 如果有環(huán)，如何找到這個(gè)環(huán)的入口
判斷鏈表是否有環(huán)：
可以使用快慢指針法，分別定義 fast 和 slow 指針，從頭結(jié)點(diǎn)出發(fā)，fast指針每次移動(dòng)兩個(gè)節(jié)點(diǎn)，slow指針每次移動(dòng)一個(gè)節(jié)點(diǎn)，如果 fast 和 slow指針在途中相遇 ，說明這個(gè)鏈表有環(huán)。
為什么fast 走兩個(gè)節(jié)點(diǎn)，slow走一個(gè)節(jié)點(diǎn)，有環(huán)的話，一定會在環(huán)內(nèi)相遇呢，而不是永遠(yuǎn)的錯(cuò)開呢
首先第一點(diǎn)：fast指針一定先進(jìn)入環(huán)中，如果fast指針和slow指針相遇的話，一定是在環(huán)中相遇，這是毋庸置疑的。
題目思路：這道題目可以使用雙指針法求解。大致的思路是首先通過兩次遍歷得到兩個(gè)鏈表的長度，然后計(jì)算出兩個(gè)鏈表的長度差值。然后在較長的鏈表上先行走這個(gè)差值的步數(shù)，然后兩個(gè)指針再同時(shí)遍歷，如果有相交的節(jié)點(diǎn)，那么最終兩個(gè)指針一定會在相交節(jié)點(diǎn)處相遇。如果沒有相交的節(jié)點(diǎn)，那么兩個(gè)指針會同時(shí)到達(dá)鏈表的末尾。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
time: O(n+m) 其中n和m分別是兩個(gè)鏈表的長度。
space: O(1)
"""
if headA is None or headB is None:
return None
lenA, lenB = 0, 0
nodeA, nodeB = headA, headB
# 計(jì)算鏈表A的長度
while nodeA:
lenA += 1
nodeA = nodeA.next
# 計(jì)算鏈表B的長度
while nodeB:
lenB += 1
nodeB = nodeB.next
nodeA, nodeB = headA, headB
# 如果鏈表A長于鏈表B，則先在鏈表A上走lenA - lenB步
if lenA > lenB:
for i in range(lenA - lenB):
nodeA = nodeA.next
# 如果鏈表B長于鏈表A，則先在鏈表B上走lenB - lenA步
elif lenB > lenA:
for i in range(lenB - lenA):
nodeB = nodeB.next
# 兩個(gè)指針同時(shí)走，如果存在相交節(jié)點(diǎn)，那么兩個(gè)指針一定會在相交節(jié)點(diǎn)處相遇
while nodeA != nodeB:
nodeA = nodeA.next
nodeB = nodeB.next
return nodeA
142. 環(huán)形鏈表 II
給定一個(gè)鏈表的頭節(jié)點(diǎn) ?head?，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。?如果鏈表無環(huán)，則返回?null。
如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識鏈表的實(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
解釋：鏈表中沒有環(huán)。
?提示：
鏈表中節(jié)點(diǎn)的數(shù)目范圍在范圍 [0, 104] 內(nèi)
-105 <= Node.val <= 105
pos 的值為 -1 或者鏈表中的一個(gè)有效索引
?進(jìn)階：你是否可以使用 O(1) 空間解決此題？
這道題分兩點(diǎn)：
1. 找到是否有環(huán)? 2.如果有環(huán)，找到環(huán)的入口
這道題的解題思路為：
使用雙指針，一個(gè)快指針（每次移動(dòng)兩個(gè)節(jié)點(diǎn)）和一個(gè)慢指針（每次移動(dòng)一個(gè)節(jié)點(diǎn)）。如果鏈表中有環(huán)，那么這兩個(gè)指針一定會在環(huán)中的某個(gè)位置相遇。
在這兩個(gè)指針相遇后，我們將快指針重置到鏈表的頭部，并將快慢指針的移動(dòng)速度都設(shè)為一次一個(gè)節(jié)點(diǎn)，然后繼續(xù)移動(dòng)，當(dāng)它們再次相遇時(shí)，相遇的位置就是環(huán)的入口。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
time: O(n)
space: O(1)
"""
# 找鏈表中環(huán)的入口。需要確保鏈表至少有兩個(gè)節(jié)點(diǎn)，這樣才可能存在一個(gè)環(huán)。
# 如果鏈表中只有一個(gè)節(jié)點(diǎn)（或者沒有節(jié)點(diǎn)），那么就不存在環(huán)，我們就可以直接返回 None。
if head is None or head.next is None:
return None
slow = head
fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# If there is a cycle, the slow and fast pointers will eventually meet
if (fast == slow):
# Move one of the pointers back to the start of the list
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return fast
# If there is no cycle, return None
return None
-
定義兩個(gè)指針：
fast和slow，分別初始化為鏈表的頭部。 -
在一個(gè)循環(huán)中，移動(dòng)
fast指針兩步，slow指針一步。如果鏈表中存在環(huán)，那么這兩個(gè)指針最終會在環(huán)中的某個(gè)位置相遇。 -
當(dāng)發(fā)現(xiàn)
fast和slow相遇時(shí)，將fast指針重新設(shè)置為鏈表的頭部，并開始以同樣的速度移動(dòng)fast和slow。文章來源：http://www.zghlxwxcb.cn/news/detail-552838.html -
當(dāng)
fast和slow再次相遇時(shí)，它們會在環(huán)的入口相遇。這時(shí)返回fast或slow都可以，因?yàn)樗鼈兌贾赶颦h(huán)的入口。文章來源地址http://www.zghlxwxcb.cn/news/detail-552838.html
到了這里，關(guān)于Day 4 鏈表: 24. 兩兩交換鏈表中的節(jié)點(diǎn), 19.刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn), 面試題 02.07. 鏈表相交 ，142.環(huán)形鏈表II的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
