目录
- 链表相关算法建议
- 203.移除链表元素
- 237.删除链表中的节点
- 206.反转一个单链表
- 2.两数相加
- 160.相交链表
- 86.分隔链表
- 234.回文链表
- 141.环形链表
- 21.合并两个有序链表
- 23.合并K个升序链表
链表相关算法建议
一、解题建议
一定要多画图
二、解题技巧
虚拟头结点
快慢指针
多指针
……
三、常用代码要非常熟练
链表节点的插入、删除
反转（翻转）一个链表
快慢指针求中心节点
计算链表的长度
……
203.移除链表元素
题目描述
_203_移除链表元素 - https://leetcode-cn.com/problems/remove-linked-list-elements/
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
题目实现
时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
//虚拟头结点
ListNode * dummyHead = new ListNode(0,head);
//扫描节点
ListNode * curNode = dummyHead;
while (curNode->next) {
if (curNode->next->val == val) {
curNode->next = curNode->next->next;
}else{
curNode = curNode->next;
}
}
return dummyHead->next;
}
};
237.删除链表中的节点
题目描述
237. 删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
示例 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.
提示：
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。
题目实现
时间复杂度O(1),空间复杂度O(1)
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
};
206.反转一个单链表
题目描述
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、递归方式
时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
二、迭代方式
时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode * newHead = nullptr;
while (head) {
ListNode* temp = head->next;
head->next = newHead;
newHead = head;
head = temp;
}
return newHead;
}
};
2.两数相加
题目描述
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
class Solution {
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var head1 = l1
var head2 = l2
var param = 0
var preHead = ListNode()
var currentNode = preHead
while head1 != nil || head2 != nil {
var val1 = 0
if head1 != nil {
val1 = head1!.val
head1 = head1!.next
}
var val2 = 0
if head2 != nil {
val2 = head2!.val
head2 = head2!.next
}
let sum = val1 + val2 + param
let node = ListNode()
if sum >= 10 {
node.val = sum - 10
param = 1
} else {
node.val = sum
param = 0
}
currentNode.next = node
currentNode = node
}
if param > 0 { currentNode.next = ListNode(param) }
return preHead.next
}
}
//时间复杂度O(n),空间复杂度O(n) (n l1与l2d中较长的链表长度）
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int carray = 0;//进位默认为0
ListNode * dummyHead = new ListNode(0);//虚拟头结点
ListNode * curNode = dummyHead;//扫描节点
while (l1 || l2) {
int v1 = 0;
if (l1) {
v1 = l1->val;
l1 = l1->next;
}
int v2 = 0;
if (l2) {
v2 = l2->val;
l2 = l2->next;
}
int sum = v1 + v2 + carray;
curNode->next = new ListNode(sum%10);
carray = sum / 10;
curNode = curNode->next;
}
if (carray >0) {
curNode->next = new ListNode(carray);
}
return dummyHead->next;
}
};
160.相交链表
题目描述
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
//时间复杂度O(1),空间复杂度O(n+m) (n:headA的长度，m:headB的长度）
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode * trailA = headA;
ListNode * trailB = headB;
while (trailA != trailB) {
trailA = (trailA == nullptr) ? headB : trailA->next;
trailB = (trailB == nullptr) ? headA : trailB->next;
}
return trailA;
}
};
86. 分隔链表
题目描述
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
//时间复杂度O(1),空间复杂度O(n) (n:head链表长度）
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if (head == nullptr || head->next == nullptr) return head;
ListNode * headA = new ListNode(0);
ListNode * trailA = headA;
ListNode * headB = new ListNode(0);
ListNode * trailB = headB;
ListNode * trailNode = head;
while (trailNode) {
if (trailNode->val < x) {
trailA->next = trailNode;
trailA = trailA->next;
}else{
trailB->next = trailNode;
trailB = trailB->next;
}
trailNode = trailNode->next;
}
trailB->next = nullptr;
trailA->next = headB->next;
return headA->next;
}
};
234.回文链表
题目描述
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
//时间复杂度O(1),空间复杂度O(n) (n:head链表长度）
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) return true;
if (head->next->next == nullptr) return head->val == head->next->val;
//获取中间节点
ListNode * mid = midNode(head);
//反转右半部分
ListNode * rHead = reverseLinkList(mid->next);
//不破坏原有链表结构
ListNode * lHead = head;
//
ListNode * oldRHead = rHead;
bool result = true;
while (rHead) {
if (lHead->val != rHead->val) {
result = false;
break;
}
lHead = lHead->next;
rHead = rHead->next;
}
//不破坏原有的链表结构，将oldRHead再反转回来
reverseLinkList(oldRHead);
return result;
}
/// 获取链表的中间节点（快慢指针）
/// @param head 链表
ListNode * midNode(ListNode* head){
if(head == nullptr) return nullptr;
ListNode * slowNode = head;
ListNode * fastNode = head->next;
while (fastNode && fastNode->next) {
fastNode = fastNode->next->next;
slowNode = slowNode->next;
}
return slowNode;
}
/// 反转一个链表，返回新的链表
/// @param head 链表
ListNode* reverseLinkList(ListNode* head){
ListNode * newHead = nullptr;
while (head) {
ListNode * temp = head->next;
head->next = newHead;
newHead = head;
head = temp;
}
return newHead;
}
};
141.环形链表
题目描述
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
class Solution {
public:
bool hasCycle(ListNode *head) {
//思路：快慢指针
//空链表或链表只有一个节点时，返回false
if (head == nullptr || head->next == nullptr) return false;
//避免起始时两个指针指向相同
ListNode* slow = head; //慢指针指向首个节点
ListNode* fast = head->next; //快指针指向第二个节点
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
};
21.合并两个有序链表
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
迭代方式实现
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//创建一个虚拟头结点
ListNode * dummyHead = new ListNode(0);
ListNode * current = dummyHead;
while (l1 && l2) {
if (l1->val < l2->val) {
current->next = l1;
l1 = l1->next;
}else{
current->next = l2;
l2 = l2->next;
}
current = current->next;
}
if (l1) {
current->next = l1;
}else{
current->next = l2;
}
return dummyHead->next;
}
};
递归方式实现
//递归方式实现
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}else{
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
23.合并K个升序链表
题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
实现方式一：两两合并
class Solution {
ListNode * dummyHead = new ListNode(0);
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//创建一个虚拟头结点
dummyHead->next = nullptr;
ListNode * current = dummyHead;
while (l1 && l2) {
if (l1->val < l2->val) {
current->next = l1;
l1 = l1->next;
}else{
current->next = l2;
l2 = l2->next;
}
current = current->next;
}
if (l1) {
current->next = l1;
}else{
current->next = l2;
}
return dummyHead->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
for (int i = 1; i<lists.size(); i++) {
lists[0] = mergeTwoLists(lists[0], lists[i]);
}
return lists[0];
}
};
实现方式二：一轮一轮进行，每轮挑出最小的
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode * head = new ListNode(0);
ListNode * current = head;
while (true) {
//找出最小的节点
int minIndex = -1;
for (int i = 0; i<lists.size(); i++) {
if(lists[i] == nullptr) continue;
if (minIndex == -1 || lists[i]->val < lists[minIndex]->val) {
minIndex = i;
}
}
//链表数组已经全部为nullptr
if(minIndex == -1) break;
current->next = lists[minIndex];
current = current->next;
//更新链表数组的值
lists[minIndex] = lists[minIndex]->next;
}
return head->next;
}
};
行者常至，为者常成！