24. 兩兩交換鏈表中的節(jié)點 - 力扣（LeetCode）
模擬題衅疙，注意保存好中間值
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy_head = ListNode(next=head)
cur = dummy_head
while cur.next is not None and cur.next.next is not None:
temp1 = cur.next
temp2 = cur.next.next.next
cur.next = cur.next.next
cur.next.next = temp1
temp1.next = temp2
cur = cur.next.next
return dummy_head.next
19. 刪除鏈表的倒數(shù)第 N 個結(jié)點 - 力扣（LeetCode）
解題思路
- 鏈表不像數(shù)組可以直接用下標莲趣，只能依靠指針一個個往下。
- 雙指針解法饱溢，快慢指針同時指向虛擬頭節(jié)點喧伞，快指針先走n步，然后快慢指針一起往前，直到快指針指向最后一個節(jié)點絮识，此時慢指針指向的節(jié)點的next就是要刪除的
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy_head = ListNode(next=head)
slow, fast = dummy_head, dummy_head
for i in range(n):
fast = fast.next #先讓fast移動n個位置
while fast.next is not None:
slow = slow.next # slow.next指向的就是倒數(shù)n個
fast = fast.next #當fast.next移動到鏈表最后一個
slow.next= slow.next.next
return dummy_head.next
- 因為用了虛擬頭節(jié)點绿聘，所以最后慢指針指向的是目標刪除節(jié)點的前一個
面試題 02.07. 鏈表相交 - 力扣（LeetCode）
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
cur = headA
n1 = 0
while cur:
cur = cur.next
n1 += 1
cur = headB
n2 = 0
while cur:
cur = cur.next
n2 += 1
if n1 > n2:
cur1 = headA #1長2短
cur2 = headB
else:
cur1 = headB
cur2 = headA
for i in range(abs(n1-n2)):
cur1 = cur1.next
while cur1 :
if cur1 == cur2:
return cur1
cur1 = cur1.next
cur2 = cur2.next
return None
- 注意邊界和計數(shù)；cur=cur.next是移動一次次舌，count要加上1
142. 環(huán)形鏈表 II - 力扣（LeetCode）
解題思路
- 雙指針，快指針走兩步兽愤，慢指針走一步彼念，若相遇，一定是在環(huán)內(nèi)浅萧，且慢指針一定沒走滿一圈
- 找到相遇點之后逐沙，設(shè)置兩個新指針，一個從head出發(fā)洼畅，一個從相遇點出發(fā)吩案，相遇時的節(jié)點就是環(huán)入口（數(shù)學證明見代碼隨想錄 (programmercarl.com)）
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
fast = slow = head
while fast is not None and fast.next is not None:
fast = fast.next.next #快指針兩步一走
slow = slow.next # 慢指針一步一走，若相遇帝簇，必有環(huán)徘郭，且在環(huán)內(nèi)相遇
if fast == slow: #相遇點
index1 = head #新雙指針，從頭出發(fā)
index2 = fast # 從相遇點出發(fā)
while index1 != index2:
index1 = index1.next
index2 = index2.next
return index1 #環(huán)起點
return None
