算法通关村第一关——链表经典问题之寻找两个链表的第一个公共结点

这篇具有很好参考价值的文章主要介绍了算法通关村第一关——链表经典问题之寻找两个链表的第一个公共结点。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

这是一道经典的链表问题,来自剑指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

#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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法通关村第一关——链表经典问题之双指针专题笔记

    我一直觉得双指针是一个非常好用的方法,在链表中可以使用,在数组中依然可以,很灵活。 1. 寻找中间结点         用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步, fast 一次走两步。那么当 fast 到达链表的末尾时,slow 必然位于中间。 2. 寻找倒数第K个元素 在这

    2024年02月15日
    浏览(40)
  • 算法通关村第一关——链表经典问题之第一个公共子节点笔记

    题目:剑指 Offer 52. 两个链表的第一个公共节点 输入两个链表,找出它们的第一个公共节点。 如下面的两个链表: 在节点 c1 开始相交。 链表节点的定义 小技巧: 如果题目刚拿到手的时候没有思路怎么办? 试着将常用的数据结构和常用的算法思想都想一遍,一个一个靠,看

    2024年02月16日
    浏览(49)
  • Java 算法篇-链表的经典算法:判断回文链表、判断环链表与寻找环入口节点(“龟兔赛跑“算法实现)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍       文章目录         1.0 链表的创建         2.0 判断回文链表说明         2.1 快慢指针方法         2.2 使用递归方式实现反转链表方法         2.3 实现判断回文链表 - 使用快慢指针与反转链表

    2024年02月05日
    浏览(62)
  • 算法通关村第一关--链表青铜挑战笔记

    开始时间:2023年7月16日20:45:26 什么是链表,链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是hea

    2024年02月17日
    浏览(43)
  • 算法通关村第一关 | 链表青铜挑战笔记

    一、 什么是链表? 链表是一种比较简单、很常见的数据结构,是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 二、链表的特点 链表是一种比较简单、很常见的数据结构,是线性表(List)的一种,是一种物理存

    2024年02月14日
    浏览(38)
  • 算法通关村第一关-链表青铜挑战笔记

    平时我们一般都是用数组,每个数组都会有一个相对应的索引,这样就使得数组能够方便的调用出对应索引得到需要的数据,但是这也造成了一个问题,那就是不好在数组中插入或者删除一个数据,例如 int arr[]={1,2,4,5}如果我想在数组中的2和4中添加一个数据3 那么我们首先就

    2024年02月15日
    浏览(42)
  • 算法通关村第一关——链表青铜挑战笔记

    链表的基本单元就是 节点 ,也就是说链表是由一个一个节点构成的。 而对于节点来说,里面至少会包含一个 指针 和一个 数据元素 ,也就是如下图所示: 其中数据域用来存放数据元素,指针域用来存放指向下一个节点的指针,这样一个一个连接起来的就是链表。如下图所

    2024年02月16日
    浏览(42)
  • 算法通关村第一关———链表青铜挑战笔记

    通过类来构建节点,用next指针将节点连起来。 会有插入位置的范围问题,不能超出链表范围 会有删除位置的范围问题 构造双向链表 插入和删除都有三种情况,头中尾  

    2024年02月15日
    浏览(43)
  • 《算法通关村第一关——链表青铜挑战笔记》

    链表中每个结点内部的“生态环境”。 数据域存储元素的值,指针域存放指针。 示例: c语言构造链表 可分为三步 1.创建头指针。 2.创建头结点,使头指针指向头结点。 3.循环创建结点,并使前一个结点指向当前结点。 1.)创建结点。 2.)使前一个结点指向当前结点。 3.)

    2024年02月15日
    浏览(39)
  • 编程导航算法通关村第一关|青铜|链表基础

    JVM有栈区和堆区 栈区:存引用,就是指向实际对象的地址。。 堆区:存的是创建的对象。 定义 规范的链表定义 LeetCode算法题中常用 遍历 插入 删除 结点 结构遍历 插入 从头插入 从尾插入 从某个值为key的节点后面插入 删除 删除头结点 删除尾结点 按值删除

    2024年02月15日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包