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