24. 两两交换链表中的节点 - 力扣（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. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
解题思路
- 链表不像数组可以直接用下标，只能依靠指针一个个往下。
- 双指针解法，快慢指针同时指向虚拟头节点，快指针先走n步，然后快慢指针一起往前，直到快指针指向最后一个节点，此时慢指针指向的节点的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指向的就是倒数n个
fast = fast.next #当fast.next移动到链表最后一个
slow.next= slow.next.next
return dummy_head.next
- 因为用了虚拟头节点，所以最后慢指针指向的是目标删除节点的前一个
面试题 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
- 注意边界和计数；cur=cur.next是移动一次，count要加上1
142. 环形链表 II - 力扣（LeetCode）
解题思路
- 双指针，快指针走两步，慢指针走一步，若相遇，一定是在环内，且慢指针一定没走满一圈
- 找到相遇点之后，设置两个新指针，一个从head出发，一个从相遇点出发，相遇时的节点就是环入口（数学证明见代码随想录 (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 # 慢指针一步一走，若相遇，必有环，且在环内相遇
if fast == slow: #相遇点
index1 = head #新双指针，从头出发
index2 = fast # 从相遇点出发
while index1 != index2:
index1 = index1.next
index2 = index2.next
return index1 #环起点
return None
