1.两个链表的第一个公共结点
输入两个链表,找出它们的第一个公共结点。
当不存在公共节点时,返回空节点。
数据范围
链表长度 [1,2000]。
样例
给出两个链表如下所示:
A:
····· a1 → a2
····· · ······ ↘
····················· c1 → c2 → c3
··················· · ↗
······ b1 → b2 → b3
B:
输出第一个公共节点c1
时间复杂度
循环链表 o(n)
注意:
没有公共节点,也会同时走到对方的NULL而相等的
为什么我运行if(p -> next)会错呢?
因为要考虑二者没有相交的情况,这个时候返回要让两个指针都指向尾部的null,要是写成(p->next)会发现自始至终指针没有指向尾部的NULL
代码
思想:
两个链表设为L1,L2.从头遍历,当L1到达末尾时,接着更新为L2的第一个结点
当L2到达末尾时,接着更新为L1的第一个结点,一边遍历一边比较,直到L1遍历的节点与L2同结束。
核心思想:就是让两个链表进行等长的同步遍历
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
ListNode* p=headA;
ListNode* q=headB;
while(p!=q)
{
if(p)
{
p=p->next;
}
else
{
p=headB;
}
if(q)
{
q=q->next;
}
else
{
q=headA;
}
}
//如果它们本来就没有公共节点时
//最晚在链表交替后的那次会同时为空结束循环,此时返回空指针代表没有公共节点
return q;
}
};
2.删除链表的倒数第N个节点
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1
输出:[]
示例 3:
输入:head = [1,2], n = 1
输出:[1]
提示:
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
时间复杂度
O(n)
双指针的经典应用,如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了。
代码:
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode*dummy = new ListNode(-1);
dummy->next=head;
ListNode*slow=dummy;
ListNode*fast=dummy;
//若head为带头节点,直接slow=fast=head即可
while(n--)
{
fast=fast->next;
}
//该条件为让slow少走一步,指向前驱节点
while(fast->next)
{
fast=fast->next;
slow=slow->next;
}
ListNode*tmp=slow->next;
slow->next=tmp->next;
delete tmp;
return dummy->next;
}
};
3.交换链表中的节点
给你链表的头节点 head 和一个整数 k 。
交换 链表正数第 k 个节点和倒数第 k 个节点的值后,返回链表的头节点(链表 从 1 开始索引)。
输入:head = [1,2,3,4,5], k = 2
输出:[1,4,3,2,5]
输入:head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出:[7,9,6,6,8,7,3,0,9,5]
双指针,交换值即可
代码
class Solution {
public:
ListNode* swapNodes(ListNode* head, int k) {
ListNode*dummy=new ListNode(-1);
dummy->next=head;
ListNode*fast=dummy;
ListNode*slow=dummy;
ListNode*change=dummy;
for(int i=0;i<k;i++)
{
change=change->next;
fast=fast->next;
}
while(fast->next)
{
slow=slow->next;
fast=fast->next;
}
//因为while(fast->next)slow指向倒数第k个节点的前一个,所有在next一次
slow=slow->next;
swap(slow->val,change->val);
return dummy->next;
}
};
4.链表中倒数第k个节点
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。
例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例:
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
时间复杂度:
O(n)
代码
class Solution {
public:
//head为带与不带头结点代码同
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode*slow=head;
ListNode*fast=head;
while(k--)
{
fast=fast->next;
}
while(fast) //为什么这里变为fast->next就不可以呢,因为若只有三个元素,k=3,此时k已经变成了null,如何判断null的下一//个,所以出现错误,不行,但使用虚拟节点开头就可以,因为始终多一个点,k不能超过链表的节点(不包括虚拟节//点的数量)
{
slow=slow->next;
fast=fast->next;
}
if(slow!=head)
{
return slow;//查找成功
}
return NULL;
}
};
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode*dummy=new ListNode(0);
dummy->next=head;
ListNode*slow=dummy;
ListNode*fast=dummy;
while(k--)
{
fast=fast->next;
}
while(fast->next)
{
slow=slow->next;
fast=fast->next;
}
slow=slow->next;
return slow;
}
};
5.链表中环的入口结点
给定一个链表,若其中包含环,则输出环的入口节点。
若其中不包含环,则输出null。
数据范围
节点 val 值取值范围 [1,1000]。
链表长度 [0,500]。
样例
QQ截图20181202023846.png
给定如上所示的链表:
[1, 2, 3, 4, 5, 6]
2
注意,这里的2表示编号是2的节点,节点编号从0开始。所以编号是2的节点就是val等于3的节点。
则输出环的入口节点3.
时间复杂度
算其指针走的次数,O(n)
slow总共走了2x+y步,fast总共走了2x+2y+x步(理想情况),所以两个指针总共走了 5x+3y 步
由于当第一次slow走到b点时,fast最多追一圈即可追上slow,所以y小于环的长度,所以 x+y 小于等于链表总长度。
代码:
class Solution {
public:
//设置两个指针,快指针一次走两步,慢指针一次一步
//快慢指针相遇,快慢指针相对速度为1,所以最多在环内一圈可追上快指针.则判断有环
ListNode *entryNodeOfLoop(ListNode *head) {
ListNode*slow=head;
ListNode*fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
slow=head;
while(slow!=fast)
{
slow=slow->next;
fast=fast->next;
}
return fast;
}
}
return NULL;
}
};
//判断是否有环:
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode*fast=head;
ListNode*slow=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;
}
};