当前位置：首页 > backend >正文

链表相关OJ题

backend 2025/9/2 6:58:28

1. 203.移除链表元素元素

203. 移除链表元素 - 力扣（LeetCode）

思路：创建一个哨兵位指向head，创建一个cur临时指针，遍历链表，遇到等于val的节点跳过即可，最后返回sentinel->next即链表的头节点

创建一个哨兵位就避免了讨论head是否为空

代码实现：

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 创建哨兵位ListNode* sentinel = new ListNode(-1);sentinel->next = head;// 创建临时指针遍历链表ListNode* cur = sentinel;// 遍历链表，跳过等于val的节点while(cur->next){if(cur->next->val == val){ListNode* tmp = cur->next;// 跳过tmp节点，并删除cur->next = cur->next->next;delete tmp;}else{cur = cur->next;}}// 创建返回值ListNode* ret = sentinel->next;delete sentinel;return ret;}
};

2. 206 反转链表

206. 反转链表 - 力扣（LeetCode）

思路：创建三个指针n1 n2 n3，n1指向空，n2指向头，n3指向头的next，三个指针不断向后移动，改变原链表的指针指向

在这里插入图片描述

class Solution {
public:ListNode* reverseList(ListNode* head) {if(head == nullptr) return nullptr;  // 考虑到链表为空的情况// 创建三个指针ListNode* n1,*n2,*n3;n1 = nullptr;n2 = head;if(head->next) n3 = head->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;// n3走到空之后就没有必要继续走了if(n3) n3 = n3->next;}return n1;}
};

注意循环条件的控制：n2走到空就结束循环，而n3的移动由自己控制，n3在最后，如果走到空，就不能再往后走了，停止移动即可

3. 876 链表的中间节点

思路：快慢指针法，快指针走两步，慢指针走一步，形成了距离差，快指针走到空，慢指针所在位置即是中间节点

在这里插入图片描述

class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode* fast, *slow;fast = slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;}
};

4. 21 合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

思路：创建一个带哨兵位的链表，同时遍历list1和list2，小的尾插到新链表上，注意：总会有一个链表先走完，另一个链表剩余节点尾插到cur之后即可

在这里插入图片描述

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* sentinel = new ListNode(-1);ListNode* cur = sentinel;while(list1 && list2){if(list1->val <= list2->val){cur->next = list1;list1 = list1->next;}else{cur->next = list2;list2 = list2->next;}cur = cur->next;}// 总会有一个链表先走完，另外一个链表剩余节点直接尾插到cur之后即可ListNode* tail = list1 == nullptr ? list2 : list1;cur->next = tail;// 返回最后拼装的节点ListNode* ret = sentinel->next;delete sentinel;return ret;}
};

5. 面试题02.04 分割链表

面试题 02.04. 分割链表 - 力扣（LeetCode）

思路：创建一个大链表和一个小链表，遍历原链表，大于等于x的节点尾插到大链表，小于x的节点尾插到小链表，小链表的尾链接大链表的头

面试题.分割链表

class Solution {
public:ListNode* partition(ListNode* head, int x) {ListNode* sentinelB = new ListNode(-1);ListNode* sentinelS = new ListNode(-1);if(head == nullptr) return nullptr;ListNode* cur = head;ListNode* curB = sentinelB;ListNode* curS = sentinelS;while(cur){if(cur->val < x){curS->next = cur;curS = curS->next;}else{curB->next = cur;curB = curB->next;}cur = cur->next;}// 处理带环问题 curB->next = nullptr;curS->next = sentinelB->next;ListNode* ret = sentinelS->next;delete sentinelB;delete sentinelS;return ret;}
};

6. OR36 回文链表

链表的回文结构_牛客题霸_牛客网

思路：逆置后半段，比较两个链表是否相同，相同即是回文链表

找中间节点：快慢指针
逆置：三个指针改变链表指向
判断回文：遍历链表

class PalindromeList {
public:// 找中间节点ListNode* midNode(ListNode* A){// 空链表处理if(A == nullptr) return nullptr;// 快慢指针ListNode* fast, *slow;fast = slow = A;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;}// 逆置链表ListNode* inverseNode(ListNode* A){// 空链表处理if(A == nullptr) return nullptr;ListNode* n1,*n2,*n3;n1 = nullptr;n2 = A;n3 = A->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3) n3 = n3->next;}return n1;}bool chkPalindrome(ListNode* A) {// 找中间节点ListNode* mid = midNode(A);// 逆置后半段ListNode* inversion = inverseNode(mid);// 遍历两个链表ListNode* curTail = inversion; // 后半段链表ListNode* curHead = A;// 前半段链表while(curHead && curTail){if(curHead->val != curTail->val){return false;}curHead = curHead->next;curTail = curTail->next;}return true;}
};

7. 160 相交链表

160. 相交链表 - 力扣（LeetCode）

在这里插入图片描述

class Solution {
public:bool isCrossing(ListNode* headA, ListNode* headB){if(headA == nullptr || headB == nullptr) return false;ListNode* curA = headA;ListNode* curB = headB;while(curA->next) curA = curA->next;while(curB->next) curB = curB->next;return curB == curA;}ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {bool ret = isCrossing(headA, headB);if(ret == false) return nullptr;// 找两个链表的长度size_t lenA = 0, lenB = 0;ListNode* curA = headA;ListNode* curB = headB;while(curA->next){++lenA;curA = curA->next;}while(curB->next){++lenB;curB = curB->next;}// 长的链表先走长度查size_t gap = std::abs(static_cast<long>(lenA - lenB));ListNode* longList = headA;ListNode* shortList = headB;if(lenB > lenA){longList = headB;shortList = headA;}while(gap--) longList = longList->next;// 现在两个链表同时走while(longList != shortList){longList = longList->next;shortList = shortList->next;}return longList;}
};

8. 141 环形链表

141. 环形链表 - 力扣（LeetCode）

思路：快慢指针，快指针会先进环，慢指针后进环
如果链表带环，快指针一定会和慢指针相遇，反之则不会

在这里插入图片描述

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

链表带环，`fast`走两步，`slow`走一步一定能追上吗？

fast先进环，slow后进环，假设slow进环时与fast距离为 $N$

每次运动，二者距离减一

这是二者距离变化：

在这里插入图片描述

所以fast走两步，slow一定能追上

链表带环，`fast`走三步，`slow`走一步一定能追上吗？

fast先进环，slow后进环，假设slow进环时与fast距离为 $N$

每次运动，二者距离减二

这是二者距离变化：

在这里插入图片描述

假设环长为 $C$ ，若 $C - 1$ 为偶数，下一轮就追上了，若 $C - 1$ 为奇数，则仍需分析

考略一下：永远追不上的条件： $C - 1$ 为奇数并且 $N$ 为奇数

这个条件能成立吗？

我们先来看一道题铺垫一下：

142. 环形链表 II - 力扣（LeetCode）

假设链表头到环的入口点距离为 $L$ ，环长 $C$ ，入口点到相遇点距离 $X$

此时fast走两步，slow走一步

相遇时：

slow 走了 $L + X$ ，

fast已经绕环 $x$ 圈，fast走了 $L + x C + X$

fast走两步，slow走一步，二者可以得到距离关系：

$L + x C + X = 2 (L + X)$

化简可得：

$L = (x - 1) C + (C - X)$

在这里插入图片描述

得到结论：一个指针从链表头开始走，一个指针从相遇点开始走，最终会在环的入口点相遇（两个指针走一样的步长）

所以，对于这道题目，先找相遇点，然后创建两个新的指针，一个从链表头开始，一个从相遇点开始，同时走，相遇的节点就是入口点

class Solution {
public:ListNode *detectCycle(ListNode *head) {// 处理空链表if(head == nullptr) return nullptr;// 创建快慢指针找相遇点ListNode* fast = head, *slow = head;// 相遇点ListNode* meet = nullptr;// 找相遇点while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(fast == slow){// 一个从链表头 一个从相遇点meet = slow;while(meet != head){meet = meet->next;head = head->next;}return meet;}}return nullptr;}
};

现在回到原来的问题，

`fast`走三步，`slow`走一步，永远追不上的条件： $C - 1$ 为奇数并且 $N$ 为奇数成立吗？

假设链表头到入口点距离 $L$ ，环长 $C$ ，slow进环时，距离fast为 $N$ ，此时fast已经走了 $x$ 圈，并多走了 $C - N$

根据数量关系可得：

$3 L = L + x C + C - N$

化简得：

$2 L = (x + 1) C - N$

$C - 1$ 为奇数，那么 $C$ 就是偶数，任意数乘以偶数还是偶数， $N$ 为奇数

根据等式：偶数 = 偶数 - 奇数这是个错误结论！所以我们之前的设想：永远追不上的猜测是错误的，fast走三步，slow走一步也可以追上！

9. 138 随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

思路：

复制原节点，构建拼接链表，例如：原链表为 $n o d e 1 - > n o d e 2 - > ...$ ，

构建拼接的链表就是 $node1->node1_{copy}->node2->node2_{copy}->...$

在这里插入图片描述

控制拷贝节点的random：拷贝节点的random是原节点random的next

在这里插入图片描述

拆下拷贝链表，尾插形成拷贝链表，并恢复原链表

在这里插入图片描述

class Solution {
public:Node* copyRandomList(Node* head) {// 1. 复制节点// 处理空链表if(head == nullptr) return nullptr;Node* cur = head;while(cur){Node* copy = new Node(cur->val);copy->next = cur->next;cur->next = copy;cur = cur->next->next;}// 2. 控制拷贝节点的randomcur = head;while(cur){Node* copy = cur->next;  if(cur->random) copy->random = cur->random->next;cur = cur->next->next;}// 3. 拆下拷贝链表 尾插形成新链表 并恢复原链表Node* sentinel = new Node(-1);Node* copyCur = sentinel;  // 用于构建新链表cur = head;while(cur){Node* copy = cur->next;Node* next = copy->next;// 尾插copyCur->next = copy;copyCur = copy;// 恢复原链表cur->next = next;cur = next;}Node* ret = sentinel->next;delete sentinel;return ret;}
};

查看全文

http://www.xdnf.cn/news/19459.html