这是一道经典的链表问题,来自剑指offer52,题目是这样的:输入两个链表,找出它们的第一个公共结点,如下图所示:
两个链表的头结点均已知,相交之后成为一个单链表,但是相交的位置未知,并且相交之前的结点数也是未知的,请设计算法找到两个链表的合并点。
第一眼看到这道题,我相信很多人都有一个共同的思路,暴力嘛,用第一个链表,用第一个链表的每一个结点与第二个结点进行比较,总能找到结果的,嗯.....方法不错,但是时间复杂度太高,排除!那接下来我就给大家介绍一下这道题可放心食用的几个经典方法,无毒无害哦!
1 哈希和集合
将第一个链表的元素全部放在Map里,之后便可以一边遍历第二个链表,一边检测哈希表判断是否遇到相同结点,主要代码如下:
Set<ListNode> set = new HashSet<();
while(p1 != NULL)
{
set.add(p1);
p1 = p1.next;
}
while(p2 != NULL)
{
if(set.contains(p2))
{
return p2;
}
p2 = p2.next;
}
return null;
2.使用栈
说到栈可能很多人很疑惑,这个竟然可以用栈吗?
当然啦,大家不要忘记栈的特性,先进后出,链表后边的结点存放在栈的上边,即当两个链表相交时,两个栈的最上面几个元素数量以及内容均是相同的,那么现在我们就可以对两个栈中的元素进行出栈操作,最后出栈(最后相同的两个元素)即链表第一个相交的结点,主要代码如下:
Stack<ListNode> stackA = new Stack();
Stack<ListNode> stackB = new Stack();
while(p1 != NULL)
{
stackA.push(p1);
p1 = p1.next;
}
while(p2 != NULL)
{
stackB.push(p2);
p2 = p2.next;
}
ListNode preNode = NULL;
while(stackB.size() > 0 && stackA.size() > 0)
{
if(stackA.peek() == stackB.peek())
{
preNode = stackA.pop();
stackB.pop();
}
else
{
break;
}
}
return preNode;
通过代码我们可以看到,通过if条件判断两个栈的栈顶元素是否相同,若相同,即更新preNode的值,并出栈,当获得最后一个相同元素时,返回这个结点。
3.双指针算法
你变成我,走过我走过的路,
我变成你,走过你走过的路,
然后我们便相遇了。
咳咳,这么浪漫的算法,我们当然要仔细的解释一下啦。我们使用两个指针 node1,node2 分别指向两个链表 headA,headB 的头结点,然后同时分别逐结点遍历,当 node1 到达链表 headA 的末尾时,重新定位到链表 headB 的头结点;当 node2 到达链表 headB 的末尾时,重新定位到链表 headA 的头结点。
这样,当它们相遇时,所指向的结点就是第一个公共结点。文章来源:https://www.toymoban.com/news/detail-603350.html
为什么会这么神奇呢?大家认真思考一下便会发现,如果两个指针在遍历完自身之后指向彼此,那么当他们第一次相遇之前,走过的路线长度是一样的,所以第一次相遇的位置便是第一个公共结点。完整代码如下:文章来源地址https://www.toymoban.com/news/detail-603350.html
#include<stdio.h>
#include<stdlib.h>
struct Listnode
{
int val;
struct Listnode* next;
};
struct Listnode* SearchFirst(struct Listnode *p1, struct Listnode *p2)
{
struct Listnode* node1 = p1;
struct Listnode* node2 = p2;
while (node1->val != node2->val)
{
node1 = node1 != NULL ? node1->next : p2;
node2 = node2 != NULL ? node2->next : p1;
}
return node1;
}
int main()
{
struct Listnode* p1 = NULL;
struct Listnode* p2 = NULL;
struct Listnode* node1 = (struct Listnode*)malloc(sizeof(struct Listnode));
struct Listnode* node2 = (struct Listnode*)malloc(sizeof(struct Listnode));
struct Listnode* node3 = (struct Listnode*)malloc(sizeof(struct Listnode));
struct Listnode* node4 = (struct Listnode*)malloc(sizeof(struct Listnode));
struct Listnode* node5 = (struct Listnode*)malloc(sizeof(struct Listnode));
struct Listnode* node6 = (struct Listnode*)malloc(sizeof(struct Listnode));
struct Listnode* node7 = (struct Listnode*)malloc(sizeof(struct Listnode));
node1->val = 1;
node2->val = 2;
node3->val = 3;
node4->val = 4;
node5->val = 5;
node6->val = 6;
node7->val = 7;
p1 = node1;
node1->next = node3;
node3->next = node4;
node4->next = node7;
p2 = node2;
node2->next = node6;
node6->next = node4;
struct Listnode* first = SearchFirst(p1, p2);
printf("%d\n", first->val);
system("pause");
return 0;
}
到了这里,关于算法通关村第一关——链表经典问题之寻找两个链表的第一个公共结点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!