C++ 数据结构与算法：线性表之链表

运行结果：

0121456

2.2.2 链表优缺点

优点：

• 内存利用：内存利用率高，不需要大块连续内存。
• 插入和删除：插入和删除节点不需要移动其他节点，时间复杂度 O(1)；
• 扩容：不需要专门进行扩容操作。

缺点：

• 内存占用量大，每个节点除了保存数据之后，还要保存一个指针。假如数组中存放 100w 个整型，内存是 400w byte; 如果用链表实现：100w*8=800w byte
• 访问：节点不连续，无法进行随机访问。
• 随机访问多：用数组，O(1)；
• 增加删除多：用链表 O(1)；

2.2.3 链表刷题

2.2.3.1 反转链表（单链表逆序）

对应了 leetcode 206 https://leetcode.cn/problems/reverse-linked-list/description/

题目描述： 示例 1： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2： 输入：head = [1,2] 输出：[2,1]

示例 3： 输入：head = [] 输出：[]

**解题思路：**将逆序和头插联系起来。力扣上是个无头链表，需要 new 一个头部，并且置空，然后将原来的链表通过头插入链表内。

p->next = head->next; head->next=p; p = q;

ListNode* reverseList(ListNode* head) {
    ListNode *newHead = new ListNode(-1, nullptr);
    ListNode *currentNode = head;
    while (currentNode != nullptr) {
        // 记录下一个节点
        ListNode *tmp = currentNode->next;
        // 头插
        currentNode->next = newHead->next;
        newHead->next = currentNode;
        currentNode = tmp;
    }
    std::unique_ptr<ListNode> ptr(newHead);
    return newHead->next;
}

2.2.3.2 删除链表倒数第 n 个节点 19

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

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

**思路：**采用双指针方式，p 和 q 同时指向 Head, 假如求倒数第 3 个节点，p 向前移动 3 个节点，然后 p q 同时移动，当 p->next 等于空时候，q 指向的就是倒数第 k 个节点的前一个节点，然后直接 q->next = q->next->next 即可；

ListNode* removeNthFromEnd(ListNode* head, int n) {
    // 这道题，可以不使用 dummy，因为相对位置不变。
    ListNode *pslow = head;
    ListNode *pfast = head;
    // p 先走 n + 1 步，指向删除的前一个
    for (int i = 0; i < n; ++i) {
        pfast = pfast->next;
    }
    // 两个一起走，知道 pfast 走到最后一个节点
    while (pfast->next != nullptr) {
        pfast = pfast->next;
        pslow = pslow->next;
    }
    // 此时 slow 指向了删除的前一个节点
    pslow->next = pslow->next->next;
    return head;
}

2.2.3.3 合并两个有序单链表 21

题目描述： 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例 2： 输入：l1 = [], l2 = [] 输出：[]

示例 3： 输入：l1 = [], l2 = [0] 输出：[0]

**解题思路：**使用双指针思想。对于无头链表，先判断哪个链表的头结点最小；然后按照顺序插入到最小的链表中。当一个链表插入完毕后，将其他直接插入进来即可。 先申请一个节点作为合并之后的节点的头部。使用两个指针 p 和 q 分别指向 link1 和 link2，遍历来比较这两个链表，将较小的元素插入到新的头部。最后，哪个不为空，newLinkCurrent->next = (p == nullptr ? q : p);

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    // 指向待插入的位置
    if (list1 == nullptr && list2 == nullptr) {
        return nullptr;
    }
    if (list1 == nullptr) {
        return list2;
    }
    if (list2 == nullptr) {
        return list1;
    }
    ListNode *phead = nullptr;
    if (list1->val < list2->val) {
        phead = list1;
        list1 = list1->next;
    } else {
        phead = list2;
        list2 = list2->next;
    }
    phead->next = nullptr;
    ListNode *ptail = phead;
    while (list1 != nullptr && list2 != nullptr) {
        if (list1->val < list2->val) {
            ptail->next = list1;
            ptail = list1;
            list1 = list1->next;
        } else {
            ptail->next = list2;
            ptail = list2;
            list2 = list2->next;
        }
    }
    // 看哪个链表提前为空
    // if (list1 != nullptr)
    // {
    //     ptail->next = list1;
    // }
    // else if (list2 != nullptr)
    // {
    //     ptail->next = list2;
    // }
    // 使用三目运算符实现
    ptail->next = (list1 != nullptr) ? list1 : list2;
    return phead;
}

2.2.3.4 环形链表 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 解释：链表中没有环。

**解题思路：**使用两个指针，快指针和慢指针，分别从头节点出发，快指针每次走两个格子，慢指针每次走一个格子，如果两个指针在途中相遇，说明这个链表有环。

**原理说明：**为什么快指针一定遇上慢指针？相对于慢指针，快指针比慢指针只多一个节点，这就相当于慢指针不移动，快指针每次走一个节点，所以快指针一定会遇到慢指针。

**数学推导：**快慢指针相遇时走过的总节点计算。 假设从头结点到环形入口节点的节点数为 x；环形入口节点到 fast 指针与 slow 指针相遇节点时的节点数量为 y。从相遇节点再到环形入口节点数为 z。

fast 走过的路径为：fast 至少走过一圈，fast 一定是追赶慢指针。 x + y + z + y slow 走过的路径为：x + y 列出等式：因为快指针每次走两步，慢指针每次走一步，所以快指针走过的路程是慢指针的两倍。 (x + y + z + y) = 2 * (x + y) x + z = 2 * x x = z 最后得到 x = z ; 说明从相遇节点再次到环的入口距离与从头结点到环的入口距离相同。

ListNode *detectCycle(ListNode *head) {
    // x = z
    ListNode *slow = head;
    ListNode *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next; // 快指针每次走两个格子
        slow = slow->next; // 慢指针每次走一个格子
        if (slow == fast) // 相遇节点
        {
            // 相遇后，慢指针从头开始走，每次走一个格子
            // 快指针从相遇位置走，每次走一个格子
            slow = head;
            while (fast != slow) {
                fast = fast->next;
                slow = slow->next;
            }
            return fast;
        }
    }
    return nullptr;
}

**代码细节：**上面代码中：while (fast != nullptr && fast->next != nullptr) 这样判断目的？ fast 不为空，这样才能访问 fast->next fast->next 不为空，这样才能访问 fast->next->next

2.2.3.6 求两个链表相交节点 160

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/

题目描述： 给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。 图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构。

**解题思路：**两个指针分别指向两个链表，分别走完后，记录下各个链表长度；len1 - len2 = diff; 长链表先走 diff 个元素，然后两个链表一起走，每次走一步都要判断是否等； 相等就是两个链表的交点

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    /* 解题思路：两个指针分别指向两个链表，分别走完后，记录下各个链表长度；len1 - len2 = diff; 长链表先走 diff 个元素，然后两个链表一起走，每次走一步都要判断是否等； 相等就是两个链表的交点 */
    // 记录 len1 和 len2 长度
    ListNode *pa = headA;
    ListNode *pb = headB;
    int len1 = 0;
    int len2 = 0;
    while (pa != nullptr) {
        len1++;
        pa = pa->next;
    }
    while (pb != nullptr) {
        len2++;
        pb = pb->next;
    }
    pa = headA;
    pb = headB;
    int diff;
    if (len1 > len2) {
        diff = len1 - len2;
        // A 先走 dif 步
        for (int i = 0; i < diff; ++i) {
            pa = pa->next;
        }
    } else {
        diff = len2 - len1;
        // A 先走 dif 步
        for (int i = 0; i < diff; ++i) {
            pb = pb->next;
        }
    }
    while (pa != nullptr && pb != nullptr) {
        if (pa == pb) {
            return pa;
        }
        pa = pa->next;
        pb = pb->next;
    }
    return nullptr;
}

**时间复杂度分析：**O(m + n),其中 m + n 分别是 headA 和 headB 的长度。

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

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

示例 1：

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

示例 2： 输入：head = [] 输出：[]

示例 3： 输入：head = [1] 输出：[1]

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

解题思路： 1 交换相邻的两个节点；

ListNode* swapPairs(ListNode* head) {
    ListNode *dummyHead = new ListNode(-1);
    dummyHead->next = head;
    ListNode *current = dummyHead;
    // 保证够两个节点
    while (current->next != nullptr && current->next->next != nullptr) {
        // 记录连续相邻的两个节点
        ListNode *temp1 = current->next;
        ListNode *temp2 = current->next->next->next;
        current->next = current->next->next; // 步骤 1
        current->next->next = temp1; // 步骤 2
        current->next->next->next = temp2; // 步骤 3
        // current 移动两位，准备下一轮交换
        current = current->next->next; // 移动两位
    }
    std::unique_ptr<ListNode> ptr(dummyHead);
    return dummyHead->next;
}

链表刷题总结

**反转链表：**使用头插入法。如果链表没有头节点，那就 new 一个头结点，使用一个指针指向头结点，另一个指针指向头的下一个节点；然后头部指针和下一个节点指针断开；当 p!=nullptr 时，依次采用头插入方式插入。核心插入如下： p->next = phead->next phead->next = p; p = p->next;

**删除倒数第 N 个节点：**使用双指针方法，头指针先移动 N 个节点，然后两个指针一起移动，判断条件时，p->next != nullptr 时，直接返回。最后 q 指向的待删除节点的前一个节点。

**链表相交：**使用双指针，各自遍历一遍链表，对比两个链表长度，长度长的链表先向前移动 diff = len1 – len2 个元素，然后一起移动；每次移动都判断是否相等，相等的就是交点。

**环形链表：**x + y + z + y = 2(x + y),最后得出 x = z,也就是快指针到相遇节点与慢指针从头到相遇节点的距离相同。