代码随想录算法训练营第四天 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II

代码随想录算法训练营第四天 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II

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

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

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

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

做这道题目时推荐大家画图感受，更加直观，不容易出现断链的错误，而且图画完了代码也就出来了，这种类型的题目在408选择题中很喜欢考察，请务必重视，养成画图的好习惯，下面给出我个人画的图：

根据所画的图我们也不难写出对应的代码。

（1）Python版本代码：

# 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):
        dummy = ListNode(0)
        dummy.next = head
        cur = dummy 
        while cur.next and cur.next.next:
            # 保存临时节点，避免断链
            temp1 = cur.next        
            temp2 = cur.next.next
            
            cur.next = temp2    # 步骤一
            temp1.next = temp2.next # 步骤二
            temp2.next = temp1  # 步骤三
            
            cur = cur.next.next # 跳两个节点进行下一步操作
        return dummy.next

（2）C++版本代码：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);  // 创建一个虚拟头节点
        dummy->next = head;
        ListNode* cur = dummy;
        while (cur->next != nullptr && cur->next->next != nullptr) {
            // 保存临时节点，避免断链
            ListNode* temp1 = cur->next;
            ListNode* temp2 = cur->next->next;

            cur->next = temp2;        // 步骤一：将 cur 的 next 指向 temp2
            temp1->next = temp2->next;  // 步骤二：将 temp1 的 next 指向 temp2 的 next
            temp2->next = temp1;      // 步骤三：将 temp2 的 next 指向 temp1
            cur = cur->next->next;    // 跳两个节点进行下一步操作
        }
        ListNode* new_head = dummy->next;
        delete dummy;  // 删除虚拟头节点
        return new_head;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

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

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

给你一个链表，删除链表的倒数第 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

**进阶：**你能尝试使用一趟扫描实现吗？

这道题目的解法跟2009年408数据结构算法题如出一辙，我们在前面的数组学习中也提到了那道题目，如下图所示：

408的这道题目和力扣的这道题目都是双指针法的经典应用，408的09年算法题只需要查找，而今天这题只是多加了一步删除操作，下面我们首先来解决408的09年的那道算法题。

2.1 2009年408算法题

（1）算法的基本设计思想：问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k个结点的位置。算法的基本设计思想:定义两个指针变量p和q，初始时均指向头结点的下一个结点(链表的第一个结点)。p指针沿链表移动，当p指针移动到第k个结点时，q指针开始与p指针同步移动;当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。

（2）算法的详细实现步骤：

①count=0，p和q指向链表表头结点的下一个结点；

②若p为空，转⑤；

③若count 等于k，则q指向下一个结点；否则，count = count + 1；

④p指向下一个结点，转②；

⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，说明k值超过了线性表的长度，查找失败，返回0；

⑥算法结束。

（3）算法实现：

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct Lnode *link;
}*LinkList;

int Search_k(LinkList list, int k){
    LinkList p=list->link,q=list->link;
    int count=0;
    while(p!=NULL){
        if(count<k) count++;
        else q=q->link;p=p->link;
    }
    if(count<k)
        return 0;
    else{
        printf("%d",q->data);
        return 1;
    }
}

2.2 LeetCode19题

这道题目的思路和上面一样，我们定义两个指针（fast 和 slow）初始都指向虚拟头节点，将 fast 指针向前移动 n 步，这样fast 和 slow 之间保持了 n 个节点的间隔，紧接着同时移动两个指针，直到 fast 指针到达链表末尾（fast.next 为 None），此时slow 指针正好指向要删除节点的前一个节点，修改 slow 指针的 next 指向，以跳过需要删除的节点，返回虚拟头节点的下一个节点作为新的头节点

（1）Python版本代码：

class Solution:
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0)  # 创建虚拟头节点
        dummy.next = head
        slow = fast = dummy  # 初始化 slow 和 fast 指针
        # 移动 fast 指针，使其与 slow 之间的间隔为 n
        while(n > 0 and fast):
            fast = fast.next
            n -= 1
        fast = fast.next
        # 同时移动 slow 和 fast，直到 fast 到达链表末尾
        while(fast):
            fast = fast.next
            slow = slow.next
        # 删除节点
        slow.next = slow.next.next

        return dummy.next  # 返回新的头节点

（2）C++版本代码：

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);  // 创建一个虚拟头节点
        dummy->next = head;
        ListNode* slow = dummy;
        ListNode* fast = dummy;

        // 移动 fast 指针，使其与 slow 之间的间隔为 n
        while (n > 0) {
            fast = fast->next;
            n--;
        }
        fast = fast->next;
        
        // 同时移动 slow 和 fast，直到 fast 到达链表末尾
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        
        // 删除节点
        ListNode* temp = slow->next;
        slow->next = slow->next->next;
        delete temp;  // 释放被删除节点的内存
        ListNode* newHead = dummy->next;
        delete dummy;  // 删除虚拟头节点，释放内存
        
        return newHead;  // 返回新的头节点
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

3 LeetCode 面试题 02.07. 链表相交

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

给你两个单链表的头节点 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) 内存的解决方案？

这道面试题目也在408的考试中出现过了，也就是2012年的408算法题，也和这题如出一辙，同样的思路同样的解决办法，下面我贴出2012年的408算法题给大家看看。

3.1 2012年408算法题

下面我给出王道官方答案：

3.2 LeetCode 面试题 02.07题

看完408的题目是不是觉得和今天的题目基本一模一样，我也挺感叹的，所以还是要好好刷题，现在我们回到力扣的题目，题目要我们求出链表交点，也就是求两个链表交点节点的指针，需要注意的是交点不是数值相等，而是指针相等，在上面的王道官方答案里面也说过，所以需要留意一下，避免出错。

我们仿照上面王道的思路，首先分别计算两个链表的长度，这一步是为了确定哪个链表更长，以及它们长度的差异，然后根据两个链表的长度差，调整较长链表的起始位置，这意味着，如果一个链表比另一个长，我们就将较长链表的头部向前移动直到两个链表从同一长度开始，也就是尾部对齐操作，接着从这个相同长度的起点开始，同时遍历两个链表，由于两个链表现在是同步的，如果它们相交，那么它们必定会在某个点拥有相同的节点，继续同步遍历直到找到两个链表相同的节点，这个节点就是交点。如果没有交点，则最终两个指针都会同时到达各自链表的末尾。

（1）Python版本代码：

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # 获取链表的长度
        def getLength(head):
            length = 0
            while head:
                length += 1
                head = head.next
            return length
        
        lenA, lenB = getLength(headA), getLength(headB)  # 计算两个链表的长度
        # 根据长度差，调整两个链表的起始位置
        while lenA > lenB:
            headA = headA.next
            lenA -= 1
        while lenB > lenA:
            headB = headB.next
            lenB -= 1

        # 同步遍历两个链表，直到找到相交节点
        while headA != headB:
            headA = headA.next
            headB = headB.next
        
        return headA  # 相交节点（如果不存在则为 None）

（2）C++版本代码：

class Solution {
public:
    // 获取链表的长度
    int getLength(ListNode* head) {
        int length = 0;
        while (head != NULL) {
            length++;
            head = head->next;
        }
        return length;
    }

    // 找到两个链表的相交节点
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        int lenA = getLength(headA);  // 链表A的长度
        int lenB = getLength(headB);  // 链表B的长度

        // 根据长度差，调整两个链表的起始位置
        while (lenA > lenB) {
            headA = headA->next;
            lenA--;
        }
        while (lenB > lenA) {
            headB = headB->next;
            lenB--;
        }

        // 同步遍历两个链表，直到找到相交节点
        while (headA != headB) {
            headA = headA->next;
            headB = headB->next;
        }

        return headA;  // 相交节点（如果不存在则为 nullptr）
    }
};

• 时间复杂度：O(n + m)
• 空间复杂度：O(1)

4 LeetCode 142.环形链表II

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

给定一个链表的头节点 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) 空间解决此题？

这道题目强烈推荐去看一下卡哥的视频讲解以及文字讲解，算是全网讲解最详细，卡哥的代码随想录关于这道题目有很多图解，大家可以去看看，由于我最近在忙于课设验收工作，所以在此就简单介绍一下两种实现思路。

4.1 快慢指针

我们使用两个指针，一个快指针（每次移动两步）和一个慢指针（每次移动一步），如果链表中存在环，快慢指针最终会在环内相遇（这里涉及一个数学推导，差不多中学知识就可以理解），找到相遇点后，将一个指针移回链表头部，另一个保持在相遇点，两个指针每次都移动一步，当它们再次相遇时，相遇点就是环的起始节点。

（1）Python版本代码

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        slow, fast = head, head
        has_cycle = False

        # 使用快慢指针检测环
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                has_cycle = True
                break

        # 如果存在环，找到环的起点
        if has_cycle:
            slow = head  # 将一个指针移回链表头部
            while slow != fast:  # 当两个指针再次相遇时，即为环的起点
                slow = slow.next
                fast = fast.next
            return slow

        return None  # 如果没有环，返回 None

（2）C++版本代码

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }
        ListNode *slow = head;
        ListNode *fast = head;
        bool hasCycle = false;

        // 使用快慢指针检测环
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }

        // 如果存在环，找到环的起点
        if (hasCycle) {
            slow = head;  // 将一个指针移回链表头部
            while (slow != fast) {  // 当两个指针再次相遇时，即为环的起点
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }

        return nullptr;  // 如果没有环，返回 nullptr
    }
};

• 时间复杂度：O(N)，这里 N 是链表的节点数，在最坏的情况下，我们需要遍历整个链表一次来确定环的起点或确认链表没有环。
• 空间复杂度：O(N)，需要额外的空间来存储已经访问过的节点，在最坏的情况下可能需要将整个链表的节点都存储在哈希表中。

4.2 哈希表

哈希表方法也算比较简单，大致思路就是遍历链表，同时将每个节点存入哈希表，每次遍历时，检查当前节点是否已存在于哈希表中，如果当前节点已存在于哈希表，说明找到了环的起点；否则，继续遍历，如果遍历完链表都没有找到环，返回 None。

（1）Python版本代码

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        visited = set()  # 创建哈希表来存储访问过的节点

        while head:
            if head in visited:  # 检查节点是否出现过
                return head      # 找到环的起点
            visited.add(head)   # 将节点添加到哈希表
            head = head.next

        return None  # 没有环

（2）C++版本代码

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> visited;  // 哈希表存储访问过的节点

        while (head != nullptr) {
            if (visited.count(head))  // 检查节点是否已在哈希表中
                return head;  // 找到环的起点
            visited.insert(head);  // 将节点加入哈希表
            head = head->next;
        }

        return nullptr;  // 没有环
    }
};

• 时间复杂度：O(N)，虽然快指针比慢指针移动得快，但在最坏的情况下，时间复杂度仍然是 O(N)，这是因为快指针最多遍历整个链表两次（第一次是找到相遇点，第二次是与慢指针一起找到环的起点）。
• 空间复杂度：O(1)，这种方法只需要常数级别的额外空间，因为它只使用了两个指针（快指针和慢指针），而不需要存储其他额外的信息。