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)。所以如果有交叉节点,那么在遍历的时候一定会相遇
- 多考虑两个指针一起遍历的方式,尝试模拟一下可能会有发现