24. 两两交换链表中的节点

用虚拟头结点，这样会方便很多。

本题链表操作就比较复杂了，建议大家先看视频，视频里我讲解了注意事项，为什么需要temp保存临时节点。

题目链接/文章讲解/视频讲解： https://programmercarl.com/0024.两两交换链表中的节点.html

思考

需要设置一个虚拟头节点，方便操作。
最好先画下图，明确指针断开重连的步骤，哪些节点需要用临时变量存起来。

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        cur = dummy
        while cur.next and cur.next.next:
            temp = cur.next
            temp1 = cur.next.next.next
            cur.next = cur.next.next
            cur.next.next = temp
            temp.next = temp1
            cur = temp
        return dummy.next

19.删除链表的倒数第N个节点

双指针的操作，要注意，删除第N个节点，那么我们当前遍历的指针一定要指向 第N个节点的前一个节点，建议先看视频。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0019.删除链表的倒数第N个节点.html

思考

设置一个虚拟头结点，方便只有一个节点时进行操作。双指针，间隔n-1步，正好可以取到倒数第n个节点的前一个节点，方便删除。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummp = ListNode(0)
        dummp.next = head
        fast = dummp
        slow = dummp
        i = 0
        while fast:
            fast = fast.next
            if i > n:
                slow = slow.next
            i+=1
        slow.next = slow.next.next
        return dummp.next

面试题 02.07. 链表相交

本题没有视频讲解，大家注意 数值相同，不代表指针相同。

题目链接/文章讲解：https://programmercarl.com/面试题02.07.链表相交.html

思考

A遍历完后，接着遍历B。B遍历完后，接着遍历A。
相交的时候，正好两种路径走的步长一样。

# 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:
        curA = headA
        curB = headB
        is_A = True
        is_B = True
        while curA and curB:
            if curA == curB:
                return curA
            if curA.next is None and is_A:
                curA = headB
                is_A = False
            else:
                curA = curA.next
            if curB.next is None and is_B:
                curB = headA
                is_B = False
            else:
                curB = curB.next
        return None

上面的代码太冗余了，实际上while的条件直接判断curA和curB是否相等就好了，如果相交，则在交点退出，如果不想交，正好在链接末尾退出。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:        
        cur_a = headA
        cur_b = headB
        while cur_a != cur_b:
            if cur_a:
                cur_a = cur_a.next
            else:
                cur_a = headB
                
            if cur_b:
                cur_b = cur_b.next
            else:
                cur_b = headA
                
        return cur_a

142.环形链表II

算是链表比较有难度的题目，需要多花点时间理解 确定环和找环入口，建议先看视频。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0142.环形链表II.html

思考

快慢指针，慢指针速度是1，快指针速度是2，速度差是1，如果有环，一定会在环内相遇。

x和z的关系如下，
x = (n - 1) (y + z) + z
在相遇点和头结点同时遍历的话，一定会在入口处再次相遇。（从相遇点出发的遍历可能会多跑n-1圈）

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while True:
            
            if fast and fast.next:
                fast = fast.next.next
            else:
                return None
            slow = slow.next
            if slow == fast:
                break
        # 相交
        new_slow = head
        while new_slow != slow:
            new_slow = new_slow.next
            slow = slow.next
        return slow