链表常见面试题C/C++
链表
文章目录
leetcode部分链表题目笔记
1. 链表反转
题目
反转一个单链表。
示例:输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
思路
(1)保留下一个节点指针,并将head->next 指向反转后的节点空间
(2)移动new_head和head指针为下一个节点反转做准备
代码
/**
* 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) {
ListNode* newhead = nullptr;
ListNode* next = nullptr;
while(head)
{
//保存next节点指针,因为接下来要指向newhead
next = head->next;
//反转链表,指向下一个
head->next = newhead;
//将newhead移动到新的链表最新位置
newhead = head;
//驱动head指针移动,为下一个节点反转做准备
head =next;
}
return newhead;
}
};
2. 链表反转(部分反转)
题目
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
思路
借鉴链表反转的思路,但是要找到部分反转链表的开始部分和结束部分,注意反转那一步分的头部,反转之后变成了尾部,需要提前记录
(1)从头结点开始,将head指针移动m-1步骤,这样head指针就指向了要反转的部分的头部,因为要涉及到反转后,反转之后和前面部分的连接,所以要记录该节点的前一个节点prehead,反转前的头结点就是反转后的尾节点modify_list_tail需要记录一下
(2)按照链表反转的思路,反转需要反转的中间部分,需要反转的节点个数为n-m+1,反转后的场景如下
(3) 反转之后需要将 反转后中间部分的链表的头尾和原来的链表切断点重新连接,前面切断部分由pre_head记录了下来,后面切断点head指针已经指向了它,而反转部分的头由new_head记录,尾部有modify_list_tail记录
代码
/**
* 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) {
ListNode* result =head;
ListNode* pre_head =nullptr;
int change_len = m-n+1;
//参数合法性检测
if(change_len<1 || head ==nullptr )
return result;
//移动m-1次找到要开始反转的开始节点
while(head && --m)
{
pre_head = head; //记录前一个节点,为后面连接座准备
head=head->next;
}
//记录开始反转的节点,因为他是反转之后的尾节点
ListNode* modify_list_tail = head;
//借鉴反转链表思路,准备反转新的链表
ListNode* new_head =nullptr;
ListNode *next =nullptr ;
while(head && change_len)
{
//先记录再反转
next = head->next;
head->next = new_head;
//移动节点,为下一次反转做准备
new_head =head;
head=head->next;
change_len --;
}
//连接结束部分的节点
modify_list_tail->next = head;
//连接开始部分
if(pre_head)//如果prehead不为空,则相当于从头节点跳过了几个节点m>1
{
pre_head->next =new_head;
}
else
{
result = new_head;
}
return result;
}
};
3. 链表交点
题目
编写一个程序,找到两个单链表相交的起始节点。如下面的两个链表:
在节点 c1 开始相交。
思路
方法1
(1)计算两个链表的长度,两个链表的长度差为delta个节点
(2)长的节点走delta步骤,长短链表的指针位置对齐
(3)对齐后同时移动两个指针,找公共交点
方法2
如下图所示,如果两个链表相交,将两个链表拼接在一起,两种拼接方式,第一行 a链表在前b链表在后,第二行b链表在前a链表在后,这两行链表的长度就相等了,如果他们有公共交点,一定在链表的后面有相同的部分
时间复杂度,空间复杂度和方法1一样,但是代码简洁了很多
方法1是通过移动头指针,让头对齐的,方法二构造新的链接方式,让新的链表尾部对齐。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//**方法1**
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//思路一: 先求长度,然后长度长的先走,对齐两个链表
//计算俩表长度
int len_a = get_list_length(headA);
int len_b = get_list_length(headB);
int delta =abs(len_a -len_b);
//移动长的链表与短的链表对齐
if(len_a>len_b)
{
while(headA && delta)
{
headA = headA->next;
delta--;
}
}
else
{
while(headB && delta)
{
headB = headB->next;
delta--;
}
}
//头指针对齐后,起头并进入找公共节点
while(headA && headB)
{
if(headA == headB) //如果有公共节点则直接返回
return headA;
headA = headA->next;
headB = headB->next;
}
return nullptr;
}
//计算链表的长度
int get_list_length(ListNode* list)
{
int len=0;
while(list)
{
len++;
list=list->next;
}
return len;
}
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//**方法1**
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//时间差不多,但是代码简洁了很多
// 思路二:定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点
// (在第一轮移动中恰好抹除了长度差)两个指针等于移动了相同的距离, 有交点就返回, 无交点
// 就是各走了两条指针的长度
if(headA == NULL || headB == NULL)
return NULL;
ListNode* a = headA;
ListNode* b = headB;
while(a != b)
{
a = a == NULL ? headB : a->next;
b = b == NULL ? headA : b->next;
}
return a;
}
};
3.环形链表交点
题目
给定一个链表,返回链表开始入环的第一个节点。
如果链表无环,则返回 null。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos是 -1,则在该链表中没有环。
说明:不允许修改给定的链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。
思路
链表的环状联系到实际中赛跑,赛跑中有套圈的现象就是因为跑到是环状的,同时还要求一个人跑的快,一个人跑得慢,即快慢指针
设置头节点到入口距离为X,快慢指针交点为距离环入口L的位置
由于快慢指针走的距离差2倍
可以得到存在K使得
(X+L)*2=X+L+CK
其中K为相遇时循环过的次数 化简可得
X+L=CK -->X=CK-L;
即存在K使得X=CK-L
对于右边CK-L,
对右边可以认为是【节点(4)绕K圈走到节点(3)的距离】
左边X,正好是(1)到(3)的距离
左边可以认为是【节点(1)到节点(3)的距离】
结合等式表示, 存在K使得【节点(4)绕k圈到节点(3)的距离】等于【节点(1)到节点(3)的距离】
代码
/**
* 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==nullptr|| head->next ==nullptr|| head->next->next==nullptr)
return nullptr;
//否则用快慢指针,找相遇的节点
ListNode* fast = head->next->next;
ListNode* slow = head->next;
//判断快慢指针合法性,注意fast要先判断,因为fast走得快,更有可能先越界,这个顺序不能换
while(fast!=nullptr && fast->next !=nullptr && slow!=nullptr)
{
if(fast ==slow) break; //如果连个节点相遇,则跳出
fast= fast->next->next;
slow =slow->next;
}
if(fast !=slow) return nullptr; //如果while循环结束,fast和slow不等,则没有相遇,没有环
//如果有环开辟一个指针从头节点开始走,与slow指针同时走,相遇的那个节点就是环的如果节点
ListNode * node =head;
while(node!=slow)
{
node =node->next; //node从头开始走,走X步到达交点,
slow = slow->next; //slow在环里面走C-L步骤到达交点,前民已经证明在快慢指针的情况下X=CK-L成立,那如果从环中相遇节点以相同速度走的话X=C-L,所以他们一定会相交
}
return node;
}
};
4. 复杂链表复制
题目
给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。 示例:
思路
方法1
//方法1,用一个map,存放原始链表节点,新复制的节点对应关系
先创建链表的节点,不考虑之间的链接关系,在打造链表之间的链接关系,链接关系通过映射关系得到,复制链表和原链表应该保持同样的映射关系,一次可以考虑hashmap
//例如<N,N’>分别代表原始节点中某个节点和拷贝后的某个节点
//如果A–>B——>c 复制时先new出来 A’,B’,C’,如果有了<A,A’>的映射
//关系,我们想要将A’–>B’这个过程就可以查找,通过A可以查找到A’,
//通过A的next就可以查找到B,查找到B了就可以查找B’
方法2
//方法2:
//方法1是通过hasMap查找到原节点与新节点之间的对于关系,这里利用链表可以相互链接的特性,将新的节点链接到原节点的后面,则通过原节点也可以对应找到新的节点
代码
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node() {}
Node(int _val, Node* _next, Node* _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
//方法1,用一个map,存放原始链表节点,新复制的节点对应关系
//例如<N,N'>分别代表原始节点中某个节点和拷贝后的某个节点
//如果A-->B——>c 复制时先new出来 A',B',C',如果有了<A,A'>的映射
//关系,我们想要将A'-->B'这个过程就可以查找,通过A可以查找到A',
//通过A的next就可以查找到B,查找到B了就可以查找B’
unordered_map <Node*,Node*> hashMap; //键:旧节点,值:新节点
Node*node =head;
while(node)
{
//new出新的节点,先不做链接
Node*tmp = new Node(node->val,0,0);
hashMap.insert(make_pair(node,tmp));
node = node->next;
}
node =head;
//从头打造链表节点之间的链接关系
while(node)
{
// N 找到N' N的next找到N’的next 打造链表链接关系
// hashMap[node]表示新链表的某个节点, hashMap[node]->next 表示新链表某个节点的下一个节点,也就是要打造前后链接关系,新链表的当前节点的下一个节点,hashMap[node->next]
hashMap[node]->next = hashMap[node->next];
hashMap[node]->random = hashMap[node->random]; node = node->next;
}
//返回复制之后的链表头部
return hashMap[head];
}
};
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node() {}
Node(int _val, Node* _next, Node* _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
//合法性检查
if(head ==nullptr)
return nullptr;
//创建新节点并链接到原节点的后面
Node *cur =head;
while(cur !=nullptr)
{
Node *tmp = new Node(cur->val,nullptr,nullptr);
//插入新节点,先链接后面,再链接前面
tmp->next = cur->next;
cur->next =tmp;
//移动到一个节点
cur= cur->next->next;
}
//根据原节点的random指针为新的节点random指针赋值,
cur =head;
while(cur !=nullptr)
{
//看当前节点是否有随机指针,如果有,则给新节点也有随机指针,新节点的随机指针,就是原节点随机指针的下一个元素
if(cur->random ==nullptr)
cur->next->random =nullptr;
else
cur->next->random = cur->random->next;
cur=cur->next->next;
}
//将原链表与拷贝新链表分离, 分离的思想就是当前节点链接到他后面的第二节点
cur =head;
Node *newHead = cur->next;//复制后新链表的头部
Node *new_cur = cur->next;
while(cur !=nullptr)
{
//原节点,隔点链接
cur->next = new_cur->next;
cur =cur->next;
//新节点隔点链接,此时原节点指针,已经跳到下次的开始,是否有后续节点需要判断,如果有后续节点,则他的后续节点也就是新的节点的下一个节点,将其链接到他的后面
if(cur ==nullptr)
new_cur->next =nullptr;
else
new_cur->next=cur->next;
new_cur = new_cur->next;
}
return newHead;
}
};
5.两个排序链表的合并
题目 (Leetcode21)
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
思路
如下图,使用一个tmp头结点,这样可以不用分别判断两个链表是否为空的情况,
在两个链表不为空的情况下判断谁小,谁小将谁链接到tmp的后面
最后还应该注意扫尾工作,当连两个链表不一样长的时候,谁有剩余就讲谁链接到最后
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//使用一个临时变量,避免判断l1,l2是否为空
ListNode tmp_head(0);
ListNode *cur = &tmp_head;
while(l1 && l2) {
if(l1->val <l2->val) { //谁小链接谁,并后移指针
cur->next = l1;
l1 = l1->next;
}
else {
cur->next =l2;
l2 = l2->next;
}
cur =cur->next;
}
//扫尾,哪个链表有剩余将哪个链表链接上去
if(l1) cur->next =l1;
if(l2) cur->next =l2;
return tmp_head.next;
}
};
6.K个排序链表合并
题目 (Leetcode23)
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。示例:输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
思路
对于多个链表合并,采用分支的思想,先分后治,
分成只有两个链表的时候再使用上例子中的两个链表的合并
- 分治思想是通过递归实现的,注意递归出口
1、输入链表个数为0,
2、输入链表个数为1,
3、输入链表个数为2.
当输入练笔个数为k时,分成【0,k/2】和【k/2,k】两部分进行合并
将两部分的最终结果再次按照两个链表合并的逻辑进行何必,得到最终合并总的排序链表
- 复杂度分析
假设链表平均长度为n,链表的个数为k
- 第一轮:
进行 k/2 次,每次两个链表融合而处理2n次,计算次数(k/2)* (2n) =kn - 第二轮:
进行 k/4 次,每次两个链表融合而处理4n次,计算次数(k/4)* (4n) =kn
。。。 - 第k轮:
进行 k/( 2^logk) 次,每次两个链表融合而处理2^logk n次,计算次数(k/( 2logk))(2logk n)=kn - 总次数 kn +kn +… +kn =kn log(k)
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
//使用分治法合并多个链表
//分支法先考虑递归出口
if(lists.size() ==0)return nullptr;
if(lists.size() ==1) return lists[0];
if(lists.size() ==2) return mergeTwoLists(lists[0],lists[1]);
//对于链表个数为其他更多的时候,采用分治思想,一份为2
int mid = lists.size()/2;
vector<ListNode*>sub_list1;
vector<ListNode*>sub_list2;
//先分
for(int i=0;i<mid;i++)
sub_list1.push_back(lists[i]);
for(int i=mid;i<lists.size();i++)
sub_list2.push_back(lists[i]);
//后治+
ListNode *l1 = mergeKLists(sub_list1);
ListNode *l2 = mergeKLists(sub_list2);
return mergeTwoLists(l1,l2);
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//使用一个临时变量,避免判断l1,l2是否为空
ListNode tmp_head(0);
ListNode *cur = &tmp_head;
while(l1 && l2) {
if(l1->val <l2->val) { //谁小链接谁,并后移指针
cur->next = l1;
l1 = l1->next;
}
else {
cur->next =l2;
l2 = l2->next;
}
cur =cur->next;
}
//扫尾,哪个链表有剩余将哪个链表链接上去
if(l1) cur->next =l1;
if(l2) cur->next =l2;
return tmp_head.next;
}
};
下一篇: 常见链表面试题