算法与数据结构学习笔记:链表
核心知识点
null异常处理
dummy node 哑巴节点
双指针/快慢指针
插入一个节点到排序链表
从一个链表中移除一个节点
翻转链表
合并两个链表
找到链表的中间节点
例题:
83. 删除排序链表中的重复元素
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:输入: 1->1->2->3->3
输出: 1->2->3
直接法:
链表是有序的,所以直接更改当前结点的 next 指针,跳过下一个结点并直接指向下一个结点之后的结点即可。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *current=head;
//null异常处理
while(current!=NULL&¤t->next!=NULL)
{
//一直删除,直到下一个不重复
// 想想如果把while改成if怎么样
//把current->next!=NULL删除会怎么样
while(current->next!=NULL&¤t->val==current->next->val)
{
current->next=current->next->next;
}
//移动到下一个节点
current=current->next;
}
return head;
}
};
时间复杂度:O(n),因为列表中的每个结点都检查一次以确定它是否重复,所以总运行时间为 O(n),其中 n是列表中的结点数。
空间复杂度:O(1),没有使用额外的空间。
82. 删除排序链表中的重复元素 II
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:输入: 1->1->1->2->3
输出: 2->3
利用哑结点 :
为了防止删除头结点的极端情况发生,先创建空结点dummy,使dummy指向传入的head结点。
然后创建一个cur指针指向dummy,比较cur的后两个结点,看他们是否相同。
如果相同,则说明cur后有重复元素,此时创建一个temp指针指向第一个重复元素,即cur->next;
通过循环进行去重,循环结束后temp指向的是这群重复元素的最后一个,依照题意此时temp的下一个才是我们想要的。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
//设置哑结点 防止删除头结点的情况发生后的问题
ListNode *dummy=new ListNode(-1);
dummy->next=head;
ListNode *cur=dummy;//cur 指向哑结点
while(cur->next!=NULL&&cur->next->next!=NULL)
{
//比较cur后两个结点
if(cur->next->val==cur->next->next->val)
{
//去重
ListNode *temp=cur->next;
while(temp->next!=NULL&&temp->val==temp->next->val)
{
temp=temp->next;
}
//temp前的重复结点都跳过了,现在我们跳过temp
cur->next=temp->next;
}
else
{
//如果cur后两个结点不重复,直接前移
cur=cur->next;
}
}
return dummy->next;
}
};
时间复杂度:O(n)
空间复杂度:O(1)
206. 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
双指针
如图,定义两个指针,pre在前 cur在后,temp 保存向前的pre指针的临时指针
每次进行一次局部翻转,
当pre到达尾部的时候终止,此时cur指向最后一个节点。
/**
* 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) {
/*定义两个指针,pre在前 cur在后
*当pre到达尾部的时候终止,此时cur指向最后一个节点
*/
ListNode *pre=head;
ListNode *cur=NULL;
ListNode *temp=NULL;
while(pre!=NULL)
{
temp=pre;//临时存储pre
pre=pre->next;//pre指向下一个节点
temp->next=cur;//翻转指针
cur=temp;//cur指针向前移动一步
}
return cur;
}
};
92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。示例:
>输入: 1->2->3->4->5->NULL, m = 2, n = 4 >输出: 1->4->3->2->5->NULL
迭代法:
参考上题,先遍历到 m 处,再翻转
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(head==NULL)
return NULL;
ListNode *pre,*cur;
pre=head;
cur=NULL;
//遍历到m节点,如果只有一个节点,跳过,这里cur会为空但是后面翻转链表的时候就不是了
while(m>1)
{
cur=pre;
pre=pre->next;
m--;
n--;
}
//m节点的前一个节点
ListNode*con=cur;
ListNode*temp=NULL;
//用于保存被翻转链表的第一个节点
ListNode*front=pre;
//反转m-n的节点
while(n--)
{
temp=pre;
pre=pre->next;
temp->next=cur;
cur=temp;
}
//如果不只是一个节点,那么就把指针指向被翻转的链表的最后一个节点
if(con!=NULL)
{
con->next=cur;
}
else
{
//否则直接输出此节点
head=cur;
}
//被翻转的链表原来的头变尾
front->next=pre;
return head;
}
};
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
迭代法:
直接连接各个节点
/**
* 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* l1, ListNode* l2) {
ListNode *dummy=new ListNode(-1);
ListNode *cur=dummy;
//将小的节点接到哑结点为头的链表中
while(l1!=NULL&&l2!=NULL)
{
if(l1->val>l2->val)
{
cur->next=l2;
cur=cur->next;
l2=l2->next;
}
else
{
cur->next=l1;
cur=cur->next;
l1=l1->next;
}
}
//处理剩下的节点
if(l1!=NULL)
{
cur->next=l1;
}
if(l2!=NULL)
{
cur->next=l2;
}
return dummy->next;
}
};
86. 分隔链表
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
当头节点不确定的时候,使用哑巴节点
将大于 x 的节点,放到另外一个链表,最后连接这两个链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if(head==NULL)
return head;
ListNode *headDummy=new ListNode(-1);
ListNode *tailDummy=new ListNode(-1);
ListNode *cur=NULL,*tail=tailDummy;
headDummy->next=head;
head=headDummy;
while(head->next!=NULL)
{
if(head->next->val<x)
{
head=head->next;
}
//这里把大于X的节点删除,然后连接到另一个链表
else
{
cur=head->next;
//删除大于X的节点
head->next=head->next->next;
//连接到新链表
tail->next=cur;
tail=tail->next;
}
}
//拼接两个链表
//tail代表tailDummy最后一个节点,它的后面可能还连着,要断掉
//如输入[1,4,3,2,5,2]就会有错,没有处理5->2
tail->next=NULL;
head->next=tailDummy->next;
return headDummy->next;
}
};
876. 链表的中间结点
给定一个带有头结点
head
的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *slow,*fast;
slow=head;
fast=head;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
};
总结:如果链表长度是偶数,返回中间偏右的位置
且fast如果初始化为head->next 返回中间偏左的位置。
奇数长度则两者相同。
148. 排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:输入: -1->5->3->4->0
输出: -1->0->3->4->5
递归
归并排序链表,找中点和合并操作
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
return mergeSort(head);
}
//寻找链表中点,快慢指针,快的到达终点,慢的刚好到中点
//当链表的长度是奇数时,slow 恰巧停在中点位置;如果长度是偶数,slow 最终的位置是中间偏右:
//此题我们让head先走,则停在中间偏左的位置
//148 143 141都有快慢指针
ListNode *findMiddle(ListNode *head)
{
ListNode *slow,*fast;
slow=head;
fast=head->next;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
//合并两个链表,参考归并排序
ListNode * mergeTwoLists(ListNode*left,ListNode*right)
{
ListNode *dummy=new ListNode(-1);
ListNode *head=dummy;
while(left!=NULL&&right!=NULL)
{
if(left->val>right->val)
{
head->next=right;
right=right->next;
}
else
{
head->next=left;
left=left->next;
}
//下一个
head=head->next;
}
//处理剩下节点
while(left!=NULL)
{
head->next=left;
head=head->next;
left=left->next;
}
while(right!=NULL)
{
head->next=right;
head=head->next;
right=right->next;
}
return dummy->next;
}
ListNode *mergeSort(ListNode *head)
{
if(head==NULL||head->next==NULL)
{
return head;
}
ListNode *middle=findMiddle(head);
// 断开中间节点
ListNode* tail=middle->next;
middle->next=NULL;
//左右分别进行归并排序
ListNode *left=mergeSort(head);
ListNode *right=mergeSort(tail);
ListNode *res=mergeTwoLists(left, right);
return res;
}
};
143. 重排链表
给定一个单链表 L:L0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
此题目为2019年计算机统考408真题
思路:找到中点断开,翻转后面部分,然后合并前后两个链表
/**
* 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:
//快慢指针找中点,同上一题
//148 143 141都有快慢指针
ListNode * findMiddle(ListNode *head)
{
ListNode *slow,*fast;
slow=head;
fast=head;
//如果是偶数个节点,返回中间偏右的位置
//你改成fast=head->next返回中间偏左也是对的
//有趣吧,画个图就知道了
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
//合并两个链表
ListNode * mergeTwoLists(ListNode* l1,ListNode*l2)
{
ListNode* dummy=new ListNode(-1);
bool toggle =true;
ListNode *head=dummy;
//间断连接两个链表
while(l1!=NULL&&l2!=NULL)
{
if(toggle)
{
head->next=l1;
l1=l1->next;
}
else
{
head->next=l2;
l2=l2->next;
}
toggle=!toggle;
head=head->next;
}
//连接剩下的节点
while(l1!=NULL)
{
head->next=l1;
l1=l1->next;
head=head->next;
}
while(l2!=NULL)
{
head->next=l2;
l2=l2->next;
head=head->next;
}
return dummy->next;
}
void reorderList(ListNode* head) {
if(head==NULL||head->next==NULL)
return ;
//找到中点 断开
ListNode *middle=findMiddle(head);
ListNode *tail=middle->next;
middle->next=NULL;
//翻转链表
ListNode *cur,*pre;
pre=tail;
cur=NULL;
while(pre!=NULL)
{
ListNode *temp=pre;
pre=pre->next;
temp->next=cur;
cur=temp;
}
tail=cur;
//合并链表
head->next=mergeTwoLists(head,tail)->next;
}
};
141. 环形链表
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
快慢指针即可,就像你在操场跑步,操场有环,只要你和她速度不一样,你们总能与她相遇,如果是直线,她到了终点,你就再也追不上她
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//148 143 141 142都有快慢指针
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==NULL)
return false;
ListNode *fast,*slow;
slow=head;
fast=head;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
// 比较指针是否相等
if(slow==fast)
return true;
}
return false;
}
};
142. 环形链表 II
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
说明:不允许修改给定的链表。
示例 :
输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。
。
Floyd 算法
你在操场跑步,操场有环,只要你和她速度不一样,你们总能与她相遇,如果是直线,她到了终点,你就再也追不上她。此题分为两个阶段,第一个阶段先用快慢指针测试是否有环,第二阶段慢指针回到头head,然后各自以相同速度前进,相遇点即为入环处(可以自己画图尝试)。严格的数学证明可参考leetcode官方题解。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head==NULL)
return NULL;
ListNode *slow,*fast;
slow=head;
fast=head;//如果这里是fast=fast->next,那么下面该怎么改?
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
//回到起点,各自以相同速度前进
slow=head;
while(slow!=fast)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
}
return NULL;
}
};
234. 回文链表
请判断一个链表是否为回文链表。
示例 1:
>输入: 1->2 >输出: false
示例 2:
>输入: 1->2->2->1 >输出: true
先找到链表中点,然后后面的翻转链表,一个个比较。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head==NULL||head->next==NULL)
return true;
ListNode *slow,*fast;
slow=head;
fast=head->next;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
//偶数长度slow是中间偏左的节点
//奇数长度slow是中点
ListNode *cur,*pre,*tail,*temp;
//分离两个链表
tail=slow->next;
slow->next=NULL;
//翻转链表
pre=tail;
cur=NULL;
while(pre!=NULL)
{
temp=pre;
pre=pre->next;
temp->next=cur;
cur=temp;
}
//原链表的最后一个节点现在变成头结点
tail=cur;
while(head!=NULL&&tail!=NULL)
{
if(tail->val!=head->val)
{
return false;
}
head=head->next;
tail=tail->next;
}
return true;
}
};
138. 复制带随机指针的链表
给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:
val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
复制节点跟在原节点后面即可
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head==NULL)
return head;
auto cur=head;
//复制节点到后面
while(cur!=NULL)
{
auto clone=new Node(cur->val);
clone->next=cur->next;
clone->random=cur->random;
cur->next=clone;
cur=clone->next;
}
//处理random指针
cur=head;
while(cur!=NULL)
{
if(cur->random!=NULL)
{
cur->next->random=cur->random->next;
}
cur=cur->next->next;
}
//分离链表
cur=head;
auto cloneHead=cur->next;
while(cur!=NULL&&cur->next!=NULL)
{
auto temp=cur->next;
cur->next=cur->next->next;
cur=temp;
}
return cloneHead;
}
};