两两交换链表节点

题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）

讲解链接：代码随想录 (programmercarl.com)

方法一：迭代模拟
关键点：
1、使用虚拟头节点，可以免于单独处理头两个翻转
2、每轮模拟维护一个cur，代表要反转的两个节点的前节点，两个节点可分别表示为cur.next和cur.next.next，然后按部就班
3、搞清楚每一步的指针变化顺序

    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_node=ListNode(next=head)
        cur=dummy_node
        while cur.next and cur.next.next:
            fw=cur.next
            bk=cur.next.next
            nx=bk.next
            bk.next=fw
            cur.next=bk
            fw.next=nx
            cur=fw
        return dummy_node.next

方法二：递归（可拓展为k个一组翻转）
关键点：
1、要明确递归函数的定义：将head为头结点的链表k个一组翻转并返回头结点
2、可以使用递归的关键：问题可分解为子问题
=>将前k个翻转+以第k+1个节点为头结点的链表k个一组翻转返回头结点+拼接

删除链表的倒数第 N 个结点

题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

讲解链接：代码随想录 (programmercarl.com)

关键点：双指针
1、使用虚拟头节点

    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy_node=ListNode(next=head)
        fast=dummy_node
        slow=dummy_node
        for i in range(n):
            fast=fast.next
        while fast.next!=None:
            slow=slow.next
            fast=fast.next
        slow.next=slow.next.next
        return dummy_node.next

链表交点

题目链接：面试题 02.07. 链表相交 - 力扣（LeetCode）

讲解链接：代码随想录 (programmercarl.com)

关键点：将两个链表尾部对齐
方法一：分别遍历计算长度差

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        lenA, lenB = 0, 0
        cur = headA
        while cur:         # 求链表A的长度
            cur = cur.next 
            lenA += 1
        cur = headB 
        while cur:         # 求链表B的长度
            cur = cur.next 
            lenB += 1
        curA, curB = headA, headB
        if lenA > lenB:     # 让curB为最长链表的头，lenB为其长度
            curA, curB = curB, curA
            lenA, lenB = lenB, lenA 
        for _ in range(lenB - lenA):  # 让curA和curB在同一起点上（末尾位置对齐）
            curB = curB.next 
        while curA:         #  遍历curA 和 curB，遇到相同则直接返回
            if curA == curB:
                return curA
            else:
                curA = curA.next 
                curB = curB.next
        return None

方法二：双指针

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        curA,curB=headA,headB
        while curA and curB:
            curA=curA.next
            curB=curB.next
        if curA:
            while curA:
                curA=curA.next
                headA=headA.next
            while headA:
                if headA==headB:
                    return headA
                headB=headB.next
                headA=headA.next
            
        elif curB:
            while curB:
                curB=curB.next
                headB=headB.next
            while headA:
                if headA==headB:
                    return headA
                headB=headB.next
                headA=headA.next
        else:
            while headA:
                if headA==headB:
                    return headA
                headB=headB.next
                headA=headA.next
            
        return        

环形链表

题目链接：142. 环形链表 II - 力扣（LeetCode）

讲解链接：代码随想录 (programmercarl.com)

关键点：快慢指针与数学计算

    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast=head
        slow=head
        while True:
            if not (fast and fast.next):
                return None 
            fast=fast.next.next
            slow=slow.next
            if fast==slow:
                break
        fast=head
        while fast!=slow:
            fast=fast.next
            slow=slow.next
        return fast