腾讯云·社区
链表常见操作总结及C++实现
链表
基本技能
- NULL异常处理
- dummy node哑巴节点
- 快慢指针
- 插入一个节点到排序链表
- 翻转链表
- 合并两个链表
- 找到链表的中间节点常见题型83. 删除排序链表中的重复元素给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* current = head;
while (current)
{
while (current->next && current->next->val == current->val)
{
ListNode* rmNode = current->next;
current->next = current->next->next;
delete rmNode;
}
current = current->next;
}
return head;
}
};82. 删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL)
return head;
// 链表头也可能删除，所以用dummy node进行辅助
ListNode dummy(0);
dummy.next = head;
head = &dummy;
while (head->next && head->next->next)
{
if (head->next->val == head->next->next->val)
{
int rmVal = head->next->val;
while (head->next && head->next->val == rmVal)
{
ListNode* rmNode = head->next;
head->next = head->next->next;
delete rmNode;
}
}
else
head = head->next;
}
return dummy.next;
}
};206. 反转链表
翻转一个单链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* reverse = NULL;
ListNode* next;
while (head)
{
next = head->next;
head->next = reverse;
reverse = head;
head = next;
}
return reverse;
}
};92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
class Solution {
public:
/**
* prev cur
* | |
* 1 -> 2 -> 3 -> 4 -> 5 -> NULL
*
* prev
* |--------------------- cur
* | | |
* 1 4 -> 3 -> 2 -> NULL 5
*/
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
for (int i = 1; i < m; ++i)
{
prev = prev->next;
}
ListNode* cur = prev->next;
ListNode* reverse = NULL;
for (int i = m; i <= n; ++i)
{
ListNode* next = cur->next;
cur->next = reverse;
reverse = cur;
cur = next;
}
prev->next->next = cur;
prev->next = reverse;
return dummy.next;
}
};25. K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
while (isNeedRevese(prev->next, k))
{
ListNode* reverse = NULL;
ListNode* cur = prev->next;
for (int i = 0; i < k; ++i)
{
ListNode* next = cur->next;
cur->next = reverse;
reverse = cur;
cur = next;
}
prev->next->next = cur;
ListNode* tmp = prev;
prev = prev->next;
tmp->next = reverse;
}
return dummy.next;
}
bool isNeedRevese(ListNode* head, int k)
{
ListNode* cur = head;
int i = 0;
for (; cur && i < k; ++i)
cur = cur->next;
return i == k;
}
};21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* p = &dummy;
while (l1 && l2)
{
if (l1->val < l2->val)
{
p->next = l1;
l1 = l1->next;
}
else
{
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
p->next = l1 ? l1 : l2;
return dummy.next;
}
};86. 分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode smallerDummy(0); // 小于x的dummy
ListNode biggerDummy(0); // 大于x的dummy
ListNode* smaller = &smallerDummy;
ListNode* bigger = &biggerDummy;
while (head)
{
if (head->val < x) {
smaller->next = head;
smaller = smaller->next;
} else {
bigger->next = head;
bigger = bigger->next;
}
head = head->next;
}
bigger->next = NULL;
smaller->next = biggerDummy.next;
return smallerDummy.next;
}
};148. 排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序
思路：归并排序，找中点和合并操作
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (head == NULL || head->next == NULL)
return head;
ListNode* mid = middle(head);
ListNode* tail = sortList(mid->next);
mid->next = NULL;
head = sortList(head);
return mergeList(head, tail);
}
ListNode* middle(ListNode* head)
{
ListNode* slow = head;
ListNode* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* mergeList(ListNode* l1, ListNode* l2)
{
ListNode dummy(0);
ListNode* p = &dummy;
while (l1 && l2)
{
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
p->next = l1 ? l1 : l2;
return dummy.next;
}
};143. 重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
class Solution {
public:
void reorderList(ListNode* head) {
if (head == NULL || head->next == NULL)
return;
ListNode* mid = middle(head);
ListNode* tail = reverseList(mid->next);
mid->next = NULL;
ListNode dummy(0);
ListNode* p = &dummy;
bool isHead = true; //是否取head链表的节点
while (head && tail) {
if (isHead) {
p->next = head;
head = head->next;
} else {
p->next = tail;
tail = tail->next;
}
p = p->next;
isHead = !isHead; // 取非，实现间或取值
}
p->next = head ? head : tail;
head = dummy.next;
}
ListNode* reverseList(ListNode* head)
{
ListNode* reverse = NULL;
while (head) {
ListNode* next = head->next;
head->next = reverse;
reverse = head;
head = next;
}
return reverse;
}
ListNode* middle(ListNode* head)
{
ListNode* slow = head;
ListNode* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};141. 环形链表
给定一个链表，判断链表中是否有环。
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
};142. 环形链表 II
证明：让两个指针其中一个从链表头 head 出发，一次走一步，让另一个指针从相遇点出发，也一次走一步，相遇点就是环的入口。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
break;
}
// 无环
if (fast == NULL ||fast->next == NULL)
return NULL;
slow = head;
while (slow != fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
};234. 回文链表
请判断一个链表是否为回文链表
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == NULL || head->next == NULL)
return true;
ListNode* mid = middle(head);
ListNode* tail = reverseList(mid->next);
mid->next = NULL;
while (head && tail)
{
if (head->val != tail->val)
return false;
head = head->next;
tail = tail->next;
}
return true;
}
ListNode* reverseList(ListNode* head)
{
ListNode* reverse = NULL;
while (head) {
ListNode* next = head->next;
head->next = reverse;
reverse = head;
head = next;
}
return reverse;
}
ListNode* middle(ListNode* head)
{
// fast如果初始化为head->next则中点在slow->next
// fast初始化为head，则中点在slow
ListNode* slow = head;
ListNode* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};138. 复制带随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 val, random_index 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
思路：1、hash 表存储指针，2、复制节点跟在原节点后面
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == NULL)
return head;
// 复制节点，紧挨到到后面
// 1->2->3 ==> 1->1'->2->2'->3->3'
Node* p = head;
while (p)
{
Node* node = new Node(p->val);
node->next = p->next;
p->next = node;
p = node->next;
}
// 处理random指针
p = head;
while (p)
{
if (p->random != NULL)
p->next->random = p->random->next;
p = p->next->next;
}
// 分离两个链表
Node dummy(0);
Node* newList = &dummy;
p = head;
while (p)
{
newList->next = p->next;
p->next = p->next->next;
newList = newList->next;
p = p->next;
}
// 原始链表头：head 1->2->3
// 克隆的链表头：newList 1'->2'->3'
return dummy.next;
}
};总结
链表必须要掌握的一些点，通过上面的练习题，基本可以应付链表类的各种题目。
原创声明，本文系作者授权云+社区发表，未经许可，不得转载。
如有侵权，请联系 yunjia_community@tencent.com 删除。
相关文章
扫码关注云+社区
领取腾讯云代金券
我来说两句