我经常搞混的点：
1. first = first.next表示的是移动first指针的位置。
如果写first.next = first.next.next，则表示的是更改链表结构，这会跳过first指针的下一个节点，改变链表本身的结构。
因此我区分清楚：仅仅需要移动first指针的位置，需要更改链表的结构。
2. while first:和while first.next:都是判断条件，两者有不同的含义。
while first:：判断的是first指针是否存在。只要first指针指向的节点（包括最后的None）存在，循环就会继续。
while first.next:：判断的是first指针的下一个节点是否存在。只有当first指针的下一个节点存在，循环才会继续。
24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：输入：head = []
输出：[]
示例 3：输入：head = [1]
输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
奇数节点最后一个节点无法两两配对，因此最后一个节点不做交换。
偶数节点两两进行交换。
仍然使用虚拟头节点的方法。定义一个dummy节点指向head，除此之外定义一个curr临时指针用于遍历整个链表。
重点：当前节点n对应的应该是curr.next, n节点的前一个节点为curr, n节点的下一个节点为curr.next.next。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
time: O(n)
space: O(1)
"""
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next is not None and curr.next.next is not None:
temp1 = curr.next # node1 temp
temp2 = curr.next.next # node2 temp
temp3 = curr.next.next.next # node3 temp
curr.next = temp2 # curr points to 2
temp2.next = temp1 # 2 points to 1
temp1.next = temp3 # 1 points to 3
curr = curr.next.next # move curr to the node before next pair
return dummy.next # dummy.next指向的是新链表的头节点19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：输入：head = [1], n = 1
输出：[]
示例 3：输入：head = [1,2], n = 1
输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
这道题的难点是找到倒数第n个节点，让后才能删除。
这道题需要用双指针的思路，定义一个快指针，再定义一个慢指针，先让快指针走n个节点，再让两个指针同时前进，直到快指针移动到null值，这个时候慢指针对应的就是将要移除的倒数第n个节点。
首先，初始化两个指针，一开始都指向头结点。然后，让第一个指针向前移动n个节点，然后两个指针同时向前移动，直到第一个指针到达末尾。此时，第二个指针所在的位置就是倒数第n个节点。在实现过程中，为了方便处理边界条件（例如删除的节点是头结点），通常会使用一个虚拟头结点。
为什么这道题可以联想到双指针解法？双指针法在解决链表问题上非常常见，尤其是涉及链表中相对位置或者需要遍历链表找到特定元素的情况。 当你需要在链表中找到某种相对位置（如中点，倒数第N个节点等）时，你可以尝试使用双指针法。在这个具体问题中，我们知道我们需要找到倒数第n个节点，这就是一个明显的相对位置问题，因此双指针法成为一个可能的解决方案。
这里比较需要重视的一点是，先让快指针走n个节点，再让两个指针同时前进，直到快指针移动到null值，这个时候慢指针对应的就是将要移除的倒数第n个节点。但是我们要删除倒数第n个节点，需要获取的是第n个节点的前一位置的curr，因此我们可以让快指针走n+1步。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
time: O(n) 只遍历了一次链表。
space: O(1) 我们只使用了两个指针fast和slow，和一个虚拟节点 dummy，它们都是常数级别的空间
"""
# 创建一个虚拟节点，并将其下一个指针设置为链表的头部
dummy = ListNode(0)
dummy.next = head
# 创建两个指针，慢指针和快指针，并将它们初始化为虚拟节点
fast = dummy
slow = dummy
# 快指针比慢指针快 n+1 步
for i in range(n+1):
fast = fast.next
# 移动两个指针，直到快速指针到达链表的末尾
while fast:
fast = fast.next
slow = slow.next
# 通过更新第 (n-1) 个节点的 next 指针删除第 n 个节点
slow.next = slow.next.next
return dummy.next
面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？
这道题需要注意的是：数值相同，不代表指针相同。
这道题目，不仅考察对链表的操作，而且还需要一些数学运算。
主要考察两知识点：
- 判断链表是否环
- 如果有环，如何找到这个环的入口
判断链表是否有环：
可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢
首先第一点：fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。
题目思路：这道题目可以使用双指针法求解。大致的思路是首先通过两次遍历得到两个链表的长度，然后计算出两个链表的长度差值。然后在较长的链表上先行走这个差值的步数，然后两个指针再同时遍历，如果有相交的节点，那么最终两个指针一定会在相交节点处相遇。如果没有相交的节点，那么两个指针会同时到达链表的末尾。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
time: O(n+m) 其中n和m分别是两个链表的长度。
space: O(1)
"""
if headA is None or headB is None:
return None
lenA, lenB = 0, 0
nodeA, nodeB = headA, headB
# 计算链表A的长度
while nodeA:
lenA += 1
nodeA = nodeA.next
# 计算链表B的长度
while nodeB:
lenB += 1
nodeB = nodeB.next
nodeA, nodeB = headA, headB
# 如果链表A长于链表B，则先在链表A上走lenA - lenB步
if lenA > lenB:
for i in range(lenA - lenB):
nodeA = nodeA.next
# 如果链表B长于链表A，则先在链表B上走lenB - lenA步
elif lenB > lenA:
for i in range(lenB - lenA):
nodeB = nodeB.next
# 两个指针同时走，如果存在相交节点，那么两个指针一定会在相交节点处相遇
while nodeA != nodeB:
nodeA = nodeA.next
nodeB = nodeB.next
return nodeA
142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
这道题分两点：
1. 找到是否有环 2.如果有环，找到环的入口
这道题的解题思路为：
使用双指针，一个快指针（每次移动两个节点）和一个慢指针（每次移动一个节点）。如果链表中有环，那么这两个指针一定会在环中的某个位置相遇。
在这两个指针相遇后，我们将快指针重置到链表的头部，并将快慢指针的移动速度都设为一次一个节点，然后继续移动，当它们再次相遇时，相遇的位置就是环的入口。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
time: O(n)
space: O(1)
"""
# 找链表中环的入口。需要确保链表至少有两个节点，这样才可能存在一个环。
# 如果链表中只有一个节点（或者没有节点），那么就不存在环，我们就可以直接返回 None。
if head is None or head.next is None:
return None
slow = head
fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# If there is a cycle, the slow and fast pointers will eventually meet
if (fast == slow):
# Move one of the pointers back to the start of the list
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return fast
# If there is no cycle, return None
return None
-
定义两个指针：
fast和slow，分别初始化为链表的头部。 -
在一个循环中，移动
fast指针两步，slow指针一步。如果链表中存在环，那么这两个指针最终会在环中的某个位置相遇。 -
当发现
fast和slow相遇时，将fast指针重新设置为链表的头部，并开始以同样的速度移动fast和slow。文章来源：https://www.toymoban.com/news/detail-552838.html -
当
fast和slow再次相遇时，它们会在环的入口相遇。这时返回fast或slow都可以，因为它们都指向环的入口。文章来源地址https://www.toymoban.com/news/detail-552838.html
到了这里，关于Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ，142.环形链表II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
