本系列是代码随想录算法训练营的学习笔记之day4，主要记录一下刷题的过程，以及核心知识点和一些值的记录的问题。

代码随想录的资源都是免费的，具体可以看参考链接【1】。

今日知识点

链表理论基础：

• 链表是一种串联、线性结构；
• 每个节点有两部分组成，值域和指针域，指针域存放指向下一个节点的指针；
• 最后一个节点的指针域指向null（注意不同语言的写法，比如python是None）；

今日题目

1. 两两交换链表中的节点（24）

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

链接：https://leetcode.cn/problems/swap-nodes-in-pairs/

解题思路

• 两两交换，跟翻转链表有点像（假设只有两个节点），只不过要复杂点（需要把多个链表链接起来）；
• 因为是两两交换，所以指针的移动间隔为1，也就是每两个节点进行一次处理，而不是顺次进行处理（循环的条件要注意）；
• 返回新链表的头节点，所以虚拟节点就很重要了；

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        vir_ln = ListNode(next=head)
        pre = vir_ln
        while pre.next and pre.next.next:
            cur = pre.next
            post = pre.next.next

            temp = post.next # 先保存下
            pre.next = post # 第一步
            post.next = cur # 第二步
            cur.next = temp # 第三步

            pre = pre.next.next # 更新指针，也就是循环条件

        return vir_ln.next

• 记住上面的顺序，然后依次修改相应节点的指针（箭头就是代表流向、指针）；
• 最后一步更新pre的时候不能直接写pre=post；

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

解题思路

• 删除不难，之前已经写过，但是对于链表来说没有像数组一样的下标，所以难点在于找到倒数第N个节点；
• 双指针法：让快慢指针相隔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]:
        vir_ln = ListNode(next=head)
        slow,fast = vir_ln,vir_ln
        while n:
            fast = fast.next
            n -= 1
        while fast.next!=None:
            slow,fast=slow.next,fast.next
        slow.next = slow.next.next
        return vir_ln.next

• 操作的指针是待删除对象的前一个，所以初始化的时候slow和fast应该是虚拟头节点；

3. 链表相交（面试题02.07）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

解题思路

• 个人感觉这道题重在理解，想象从全班随机抽取n和m个小朋友组成两个队伍（有放回的抽取），然后把两个队伍合并成一个队伍，那么如果这两个队伍中有人被抽到了两次，则这两个队伍一定能够形成一个环+尾巴的形式（也就是说两个队伍至少大于等于1个交点）；

# 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:
        if headA is None or headB is None:
            return None
        
        curA, curB = headA,headB

        while curA!=curB:
            curA = curA.next if curA else headB
            curB = curB.next if curB else headA
        
        return curA

• 链表相等指的是内存地址相等，那么相交指的就是两个节点的指针指向了同一块内存区域；

4. 环形链表（142）

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。

链接：https://leetcode.cn/problems/linked-list-cycle-ii

解题思路

• 有没有环的判断其实比较简单，就是中学物理中学的追及问题，使用双指针，让快的比慢的每次多走一步，如果存在环，那么快的最终一定会在环中某一点相遇，就好比两个人在操场跑步，跑得快的终有一刻会领先跑得慢的同学一圈，那么就是相遇了；
• 如果存在环，难点就在于找到环的入口，具体可以去看参考【1】的讲解，有数学公式上的推理，比较详细了；

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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 如果相遇
            if slow == fast:
                p = head
                q = slow
                while p!=q:
                    p = p.next
                    q = q.next
                return p

        return None

• 不要忘记了没有环的情况下返回None；

补充知识点

1. 链表的几种类型

上面说的是最简单的链表，实际上链表有几种：

• 单链表

• 双链表：一个节点有两个指针域，分别指向前一个和后一个节点；

• 循环链表：单链表的特殊情况，首尾相连。

2. 链表的存储方式

数组在内存中是连续存储的，但是链表不是，因为链表有指针，可以顺利找到下一个元素。

3. 链表与数组的性能分析

今日思考

1. 为什么在有环的情况下快慢指针一定会在环中某个节点相遇？

想象两个同学在操作跑步。。

2. 为什么存在环的时候，从头节点出发的指针一定与慢指针在环的入口相遇？

看参考【1】的数学推导。。。

参考

【1】代码随想录：https://programmercarl.com/