网站导航
> 文档中心 > 五道超经典题目，带你手撕链表题（多种方法实现）

五道超经典题目，带你手撕链表题（多种方法实现）

网友: 文档中心 2022-05-06 07:09:37

💟作者简介：大家好，我是锡兰Ceylan_，可以叫我CC ❣️    
📝个人主页：锡兰Ceylan_的博客
🏆博主信息：平凡的大一学生，有着不平凡的梦

        专栏

  • 【备战蓝桥，冲击省一】
  • 【开卷数据结构】

⚡希望大家多多支持😘一起进步~❤️
🌈若有帮助，还请【关注➕点赞➕收藏】，不行的话我再努努力💪​

94536690f848438fab30aa17191a6ea2.png

目录

🌺237. 删除链表中的节点

🍁题目描述

🍁基础框架

🍁详细思路

🍀思路一

🌺876. 链表的中间结点

🍁题目描述

🍁基础框架

🍁详细思路

🍀思路一【数组】

🍀思路二【快慢指针】

🌺剑指 Offer 24. 反转链表

🍁题目描述

🍁基础框架

🍁详细思路

🍀思路一【迭代】

🍀思路二【递归】

🌺234. 回文链表

🍁题目描述

🍁基础框架

🍁详细思路

🍀思路一【双指针】

🍀思路二【快慢指针】

🌺1669. 合并两个链表

 🍁题目描述

🍁基础框架

🍁详细思路

🍀思路一【快慢指针】

94536690f848438fab30aa17191a6ea2.png

🌺237. 删除链表中的节点

🍁题目描述

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

示例 1：

 

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2：

 

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

提示：

  •     链表中节点的数目范围是 [2, 1000]
  •     -1000 <= Node.val <= 1000
  •     链表中每个节点的值都是 唯一 的
  •     需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点

🍁基础框架

  • C++ 版本给出的基础框架代码如下：
/ * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    void deleteNode(ListNode* node) {     }};

🍁详细思路

🍀思路一

由于不能访问给定的要删除的结点前一结点，不能采用常见的删除方法。

根据题目提示，要删除的结点不是末尾结点，我们可以对删除结点的下一结点进行操作。

  • 将删除结点后面一个点的值交换到删除节点
  • 将删除节点指向删除节点后面一个点的后面一个点。

 

💬 代码演示

/ * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    void deleteNode(ListNode* node) { node->val = node->next->val; node->next = node->next->next;    }};

🌺876. 链表的中间结点

🍁题目描述

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

  •     给定链表的结点数介于 1 和 100 之间。

🍁基础框架

  • C++ 版本给出的基础框架代码如下：
/ * 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* middleNode(ListNode* head) {    }};

🍁详细思路

🍀思路一【数组】

遍历链表，将链表内元素存入数组。若数组长度为 A ，则中间结点为 A/2

💬 代码演示

/ * 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* middleNode(ListNode* head) { vector A = {head}; while (A.back()->next != NULL)     A.push_back(A.back()->next); return A[A.size() / 2];    }};

🍀思路二【快慢指针】

使用快慢指针，快指针一次走两步，满指针一次走一步。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。

💬 代码演示

/ * 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* middleNode(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast != NULL && fast->next != NULL) {     slow = slow->next;     fast = fast->next->next; } return slow;    }};

🌺剑指 Offer 24. 反转链表

🍁题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

🍁基础框架

  • C++ 版本给出的基础框架代码如下：
/ * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* reverseList(ListNode* head) {    }};

🍁详细思路

🍀思路一【迭代】

翻转链表只需要把每一个指针的指向反过来就行了，我们定义两个指针，一个指向前一结点，另一个指向当前结点，然后进行反向操作即可。

💬 代码演示

/ * 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* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr) {     ListNode* next = curr->next;     curr->next = prev;     prev = curr;     curr = next; } return prev;    }};

🍀思路二【递归】

递归三部曲

  1. 递归结束条件，
  2. 找到函数的等价关系式
  3. 调用函数

（1）当头结点或第二个结点为空的时候，返回头结点

（2）在返回的过程中，让当前结点的下一个结点的next指向当前结点，当前结点的next指向NULL，实现局部翻转。

（3）调用函数

💬 代码演示

/ * 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* reverseList(ListNode* head) { if (!head || !head->next)  {     return head; } ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = nullptr; return newHead;    }};

🌺234. 回文链表

🍁题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

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

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

🍁基础框架

  • C++ 版本给出的基础框架代码如下：
/ * 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:    bool isPalindrome(ListNode* head) {    }};

🍁详细思路

🍀思路一【双指针】

  1. 将链表中所有元素存储到容器中
  2. 使用双指针，判断是否为回文链表

💬 代码演示

/ * 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:    bool isPalindrome(ListNode* head) { vector vals; while (head != nullptr)  {     vals.push_back(head->val);     head = head->next; } for (int i = 0, j = vals.size() - 1; i < j; ++i, --j)  {     if (vals[i] != vals[j])      {  return false;     } } return true;    }};

🍀思路二【快慢指针】

为了避免O(n)的空间复杂度，我们可以改变输入，也就是改变题目所给的链表。

我们将链表的后半部分反转，再与前半部分作比较，判断是否为回文链表

  1. 使用快慢指针，快指针一次走两步，满指针一次走一步。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

  2. 反转后半部分的链表。

  3. 判断是否回文

💬 代码演示

/ * 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:    bool isPalindrome(ListNode* head) { if (head == nullptr)     return true; ListNode* halfNode = halfList(head); ListNode* endNode = reverseList(halfNode->next); ListNode* p1 = head; ListNode* p2 = endNode; while (p2 != nullptr)  {     if (p1->val != p2->val)      {  return false;     }     p1 = p1->next;     p2 = p2->next; } return true;    }    ListNode* halfList(ListNode* head) //快慢指针确立中间结点    { ListNode* fast = head; ListNode* slow = head; while (fast->next != NULL && fast->next->next != NULL)  {     slow = slow->next;     fast = fast->next->next; } return slow;    }    ListNode* reverseList(ListNode* head) //反转链表    { ListNode* prev = nullptr; ListNode* curr = head; while (curr != nullptr)  {     ListNode* nextTemp = curr->next;     curr->next = prev;     prev = curr;     curr = nextTemp; } return prev;    }};

🌺1669. 合并两个链表

 🍁题目描述

给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。

请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。

下图中蓝色边和节点展示了操作后的结果：

请你返回结果链表的头指针。

示例 1：

输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。

示例 2：

输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释：上图中蓝色的边和节点为答案链表。

提示：

  •     3 <= list1.length <= 104
  •     1 <= a <= b < list1.length - 1
  •     1 <= list2.length <= 104

🍁基础框架

  • C++ 版本给出的基础框架代码如下：
/ * 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* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {     }};

🍁详细思路

🍀思路一【快慢指针】

  1. 快指针向前遍历list1，到a点停下，做一个标记
  2. 快指针继续遍历list1，遍历到b+1点停止，插入list2
  3. 连接list1的后半部分

💬 代码演示

/ * 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* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) { int fast=0; ListNode*pre=new ListNode(0); ListNode*prehead=pre; pre->next=list1; ListNode*secondhead=list1; while(fast!=a) {     fast++;     pre=pre->next; } ListNode*first_tail=pre; while(fast!=b+1) {     fast++;     pre=pre->next; } secondhead=pre->next; ListNode*curr=list2; while(curr->next) {     curr=curr->next; } first_tail->next=list2; curr->next=secondhead; return prehead->next;}};

94536690f848438fab30aa17191a6ea2.png

本人不才，如有错误，欢迎各位大佬在评论区指正。有帮助的话还请【关注➕点赞➕收藏】，不行的话我再努努力💪💪💪   

闲鱼礼物网

网络标签：

相关问题