Day12 2022.11.18 双指针(简单)
25.合并两个排序的链表
自己实现
就用两个指针分开指向两个链表并进行遍历,比较之后放入新的列表里。
代码如下:
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==NULL)return l2;
if(l2==NULL)return l1;
ListNode* now1;
ListNode* now2;
ListNode* res;
if(l1->val>=l2->val)
{
res=new ListNode(l2->val);
now1=l1;
now2=l2->next;
}
else
{
res=new ListNode(l1->val);
now1=l1->next;
now2=l2;
}
ListNode* now0=res;
while(now1!=NULL&&now2!=NULL)
{
if(now1->val>=now2->val)
{
ListNode* tmp=new ListNode(now2->val);
now0->next=tmp;
now2=now2->next;
now0=now0->next;
}
else
{
ListNode* tmp=new ListNode(now1->val);
now0->next=tmp;
now1=now1->next;
now0=now0->next;
}
}
if(now1==NULL)now0->next=now2;
else if(now2==NULL)now0->next=now1;
return res;
}
};
代码表现
52.两个链表的第一个公共节点
自己实现
自己实现的思路就是遍历一个链表,将所有的节点都存进哈希表中,然后再遍历另一个链表,在每一个节点处在哈希表中寻找是否有该节点,这个思路比较简陋,时间关系没有实现,听Hongshuo Jia说题解很牛,直接尝试
题解
定义两个指针nowA
nowB
来遍历。nowA
遍历链表A,nowB
遍历链表B。任一指针遍历到尾节点即NULL时从另一链表的头开始继续遍历。
- 假设两个链表有交叉的节点,那么两个指针都从尾节点重置到另一节点并继续遍历后,迟早会相遇,所以把while的循环判断条件设置为
nowA != nowB
即可。跳出循环后返回nowA
就是答案。 - 如果两个链表没有交叉节点,证明第二次遍历的时候有一个指针会再次到NULL,这个时候就证明没有交叉,直接返回NULL即可。
代码如下:
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL || headB==NULL)return NULL;
ListNode* nowA=headA;
ListNode* nowB=headB;
int A=0;
int B=0;
while(nowA!=nowB)
{
nowA=nowA->next;
nowB=nowB->next;
if(nowA==NULL&&A==0)
{
nowA=headB;
A=1;
}
if(nowB==NULL&&B==0)
{
nowB=headA;
B=1;
}
if((nowA==NULL&&A==1) || (nowB==NULL&&B==1))return NULL;
}
return nowA;
}
};
代码表现
hint:
- 这个做法的灵感是通过数学恒等式得到的。假设链表A长度为a,链表B长度为b,交叉段长度为c。那么有a+(b-c) == b+(a-c)。所以如果有交叉节点,那么在遍历的时候一定会相遇
- 多考虑两个指针一起遍历的方式,尝试模拟一下可能会有发现
原文地址:http://www.cnblogs.com/cspzyy/p/16913854.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性