首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >【上篇】链表 OJ 题,原来可以这样 “盘”!

【上篇】链表 OJ 题,原来可以这样 “盘”!

作者头像
用户11872857
发布于 2025-12-17 15:52:21
发布于 2025-12-17 15:52:21
3330
举报

前言

​

在本章节中,我们将一起学习几道经典的链表相关 OJ 算法题,通过实际题目练习来巩固链表的核心知识点与编程技巧。

📚 初阶数据结构

-【 时间复杂度+空间复杂度 】

-【 顺序表 】

-【 单链表 】----


203. 移除链表元素

【题目链接】:https://leetcode.cn/problems/remove-linked-list-elements/description/

【算法原理】:

1、原地删除

用cur遍历链表,遇到值为val的节点,直接删除,但是牵扯到删除cur后就找不到后面的节点了,因此我们需要一个prev指针去记录cur节点的前一个节点,让prev和cur同步遍历

代码语言:javascript
复制
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* prev = NULL; // 用于记录当前节点cur的前一个节点,初始化为NULL(表示cur初始无前驱)
        ListNode* cur = head;  // 用于遍历链表的当前节点,从链表头开始
        
        // 遍历整个链表,直到cur为NULL(链表结束)
        while(cur) 
        {
            // 情况1:当前节点的值等于要删除的val
            if(cur->val == val) 
            {
                // 子情况1:当前节点是头节点(prev为NULL,说明cur没有前驱)
                if(prev == NULL) 
                {
                    head = cur->next;  // 头节点更新为当前节点的下一个节点(跳过当前节点)
                    delete cur;        // 释放当前节点的内存
                    cur = head;        // cur移动到新的头节点,继续遍历
                }
                // 子情况2:当前节点不是头节点(有前驱节点prev)
                else 
                {
                    prev->next = cur->next;  // 前驱节点的next直接指向当前节点的下一个节点(跳过当前节点)
                    delete cur;              // 释放当前节点的内存
                    cur = prev->next;        // cur移动到前驱节点的下一个节点(即原当前节点的下一个节点),继续遍历
                }
            }
            // 情况2:当前节点的值不等于val,无需删除,继续向前遍历
            else 
            {
                prev = cur;       // prev更新为当前节点(成为下一个节点的前驱)
                cur = cur->next;  // cur移动到下一个节点
            }
        }
        // 遍历结束,返回修改后的链表头节点
        return head;
    }
};

2、创建新链表

创建一个新链表,让值不为val的节点尾插到新链表,值为val的节点释放掉

代码语言:javascript
复制
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* Newhead = nullptr; // 新链表的头节点(最终要返回的结果)
        ListNode* cur = head; // 用于遍历原链表的当前节点指针
        ListNode* tail = nullptr; // 指向新链表的尾节点,方便尾插法添加节点

        // 遍历原链表的所有节点
        while (cur) {
            // 如果当前节点的值不是要删除的目标值,就加入新链表
            if (cur->val != val) {
                // 新链表为空时,当前节点既是头也是尾
                if (Newhead == nullptr) {
                    Newhead = tail = cur;
                } else {
                    // 新链表非空时,把当前节点接到尾节点后面,再更新尾节点
                    tail->next = cur;
                    tail = tail->next;
                }
                // 移动到原链表的下一个节点
                cur = cur->next;
            } else {
                // 如果是要删除的节点,先保存下一个节点的地址
                ListNode* next = cur->next;
                // 释放当前节点的内存
                delete cur;
                // 移动到下一个节点继续遍历
                cur = next;
            }
        }

        // 遍历结束后,新链表的尾节点要断开与原链表剩余节点的连接(防止野指针)
        if (tail) {
            tail->next = nullptr;
        }

        // 返回新链表的头节点
        return Newhead;
    }
};

206. 反转链表

【题目链接】:https://leetcode.cn/problems/reverse-linked-list/

【算法原理】:

1、原地操作

通过n1、n3这两个节点辅助,改变n2的链接关系,例:n2->next指向n1,同时向后面移动一个位置,重复操作就可以达到逆置的效果

代码语言:javascript
复制
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        if (head == nullptr)  // 空链表直接返回nullptr
            return nullptr;
        
        ListNode* n1 = nullptr;  // 指向反转后链表的前一个节点(初始为nullptr,对应原链表头的前序)
        ListNode* n2 = head;     // 指向当前需要反转的节点(初始为原链表头)
        ListNode* n3 = head->next;  // 保存当前节点的下一个节点(防止反转后断链)

        // 遍历原链表,直到当前节点n2为空
        while (n2) 
        {
            n2->next = n1;  // 反转当前节点的指向(指向n1,即前一个节点)
            
            // 三个指针依次后移,准备处理下一个节点
            n1 = n2;
            n2 = n3;
            if (n3)  // 若n3不为空,继续后移(避免空指针访问)
                n3 = n3->next;
        }

        return n1;  // 循环结束后,n1即为反转后链表的头节点
    }
};

2、创建新链表

用cur遍历链表,进行新链表的头插操作

代码语言:javascript
复制
class Solution 
{
public:
    ListNode* reverseList(ListNode* head)  
    {
        ListNode* cur = head;    // 用于遍历原链表的当前节点
        ListNode* newhead = nullptr;  // 反转后新链表的头节点(初始为空)

        // 遍历原链表所有节点
        while (cur) 
        {
            ListNode* next = cur->next;  // 保存当前节点的下一个节点(防止断链)
            
            cur->next = newhead;  // 反转当前节点指向(指向新链表的头)
            newhead = cur;        // 更新新链表头为当前节点(当前节点成为新的头)
            
            cur = next;  // 移动到原链表的下一个节点继续处理
        }

        return newhead;  // 最终newhead即为反转后链表的头节点
    }
};

876. 链表的中间节点

【题目链接】:https://leetcode.cn/problems/middle-of-the-linked-list/description/

【算法原理】:

创建两个指针,一个一次走两步,一个一次走一步,走的快的到结尾了,走的慢的就到链表中间了,但是这个题要注意边界问题,如果链表节点个数为偶数的话,fast最终会走到尾节点的下一个位置,为奇数的话走到最后一个节点

代码语言:javascript
复制
class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        ListNode* slow = head;  // 慢指针:每次移动1步
        ListNode* fast = head;  // 快指针:每次移动2步

        // 当快指针未走到链表末尾(快指针本身非空且下一个节点非空)
        while (fast && fast->next)
        {
            fast = fast->next->next;  // 快指针走2步
            slow = slow->next;        // 慢指针走1步
        }

        // 循环结束后,慢指针恰好指向中间节点
        // (若节点数为奇数,指向正中间;若为偶数,指向第二个中间节点)
        return slow;
    }
};

剑指offer22. 链表中倒数第k个节点

题目描述:输入一个链表,输出该链表中倒数第 k 个节点。为了符合大多数人的习惯,本题从 1 开始计数,即链表的尾节点是倒数第 1 个节点。 例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。 示例 1: 输入:head = [1,2,3,4,5], k = 2 输出:[4,5] 解释:链表的倒数第 2 个节点是值为 4 的节点,其后续节点为 5,故输出 [4,5]。 示例 2: 输入:head = [1], k = 1 输出:[1] 示例 3: 输入:head = [1,2], k = 3 输出:null 解释:链表长度为 2,k = 3 超出范围,返回 null。

【算法原理】:

依旧快慢指针,让快指针先走k步,这个时候快慢指针之间的距离就是k,然后快指针走到空时,慢指针的位置就是倒数第k个节点的位置,如果fast提前变成空了,说明k超出范围了,直接返回空

代码语言:javascript
复制
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        // 处理空链表的情况
        if (head == nullptr) 
        {
            return nullptr;
        }

        // 初始化快慢指针,均指向头节点
        ListNode* fast = head;
        ListNode* slow = head;

        // 快指针先向前走k步
        for (int i = 0; i < k; ++i) 
        {
            // 若快指针提前为空,说明k超过链表长度
            if (fast == nullptr) 
            {
                return nullptr;
            }

            fast = fast->next;
        }

        // 快慢指针同步移动,直到快指针到达末尾
        while (fast != nullptr) 
        {
            fast = fast->next;
            slow = slow->next;
        }

        // 此时慢指针指向倒数第k个节点
        return slow;
    }
};

21. 合并两个有序链表

【题目链接】:https://leetcode.cn/problems/merge-two-sorted-lists/description/

【算法原理】:

这道题咱们就不原地处理了,原地处理会很麻烦,而且很难想清楚

所以我们直接创建个新链表,遍历两个原链表,小的尾插到新链表,我会用两种方式演示这个思路

代码语言:javascript
复制
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 若其中一个链表为空,直接返回另一个链表
        if (list1 == nullptr) {
            return list2;
        }
        if (list2 == nullptr) {
            return list1;
        }

        ListNode* cur1 = list1;  // 遍历list1的指针
        ListNode* cur2 = list2;  // 遍历list2的指针
        ListNode* head = nullptr; // 合并后新链表的头节点
        ListNode* tail = nullptr; // 合并后新链表的尾节点,用于尾插

        // 同时遍历两个链表,直到其中一个遍历完毕
        while (cur1 && cur2) {
            // 选取值较小的节点接入新链表
            if (cur1->val < cur2->val) {
                // 新链表为空时,当前节点既是头也是尾
                if (head == nullptr) {
                    head = tail = cur1;
                } else {
                    // 新链表非空时,尾插当前节点并更新尾指针
                    tail->next = cur1;
                    tail = tail->next;
                }
                cur1 = cur1->next; // 移动list1的遍历指针
            } else {
                // 逻辑同上,处理list2的节点
                if (head == nullptr) {
                    head = tail = cur2;
                } else {
                    tail->next = cur2;
                    tail = tail->next;
                }
                cur2 = cur2->next; // 移动list2的遍历指针
            }
        }

        // 若list1还有剩余节点,直接接到新链表尾部
        if (cur1) {
            tail->next = cur1;
        }
        // 若list2还有剩余节点,直接接到新链表尾部
        if (cur2) {
            tail->next = cur2;
        }

        return head; // 返回合并后链表的头节点
    }
};

这个写法没有哨兵位,我下面写个有哨兵位的写法,写完大家可以对比下区别

代码语言:javascript
复制
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 若其中一个链表为空,直接返回另一个链表
        if (list1 == nullptr) {
            return list2;
        }
        if (list2 == nullptr) {
            return list1;
        }

        ListNode* cur1 = list1;  // 遍历list1的指针
        ListNode* cur2 = list2;  // 遍历list2的指针
        ListNode* head = new ListNode();  // 哨兵节点(简化头节点处理)
        ListNode* tail = head;  // 指向新链表尾部,用于尾插

        // 同时遍历两个链表,选取较小节点接入新链表
        while (cur1 && cur2) {
            if (cur1->val < cur2->val) {
                tail->next = cur1;  // 接入list1当前节点
                tail = tail->next;  // 尾指针后移
                cur1 = cur1->next;  // 移动list1遍历指针
            } else {
                tail->next = cur2;  // 接入list2当前节点
                tail = tail->next;  // 尾指针后移
                cur2 = cur2->next;  // 移动list2遍历指针
            }
        }

        // 拼接剩余节点(其中一个链表已遍历完)
        if (cur1) {
            tail->next = cur1;
        }
        if (cur2) {
            tail->next = cur2;
        }

        // 哨兵节点的下一个才是真正的头节点,释放哨兵节点避免内存泄漏
        ListNode* newhead = head->next;
        delete head;
        
        return newhead;  // 返回合并后链表的头节点
    }
};

经过对比发现,有哨兵位的链表尾插时不用处理头节点为空的情况,会方便一点

以上是链表OJ前5个题,下一篇文章会再讲解5个链表相关OJ题!!!

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-12-15,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • 203. 移除链表元素
  • 206. 反转链表
  • 876. 链表的中间节点
  • 剑指offer22. 链表中倒数第k个节点
  • 21. 合并两个有序链表
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档