首页 > 其他分享 >NC66 两个链表的第一个公共结点

NC66 两个链表的第一个公共结点

时间:2024-01-13 14:55:30浏览次数:34  
标签:结点 遍历 链表 NC66 l1 N1 N2 节点

https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=117&rp=1&ru=%2Fexam%2Foj&qru=%2Fexam%2Foj&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&difficulty=&judgeStatus=&tags=&title=&gioEnter=menu

代码

使用两个指针N1,N2,一个从链表1的头节点开始遍历,我们记为N1,一个从链表2的头节点开始遍历,我们记为N2。

让N1和N2一起遍历,当N1先走完链表1的尽头(为null)的时候,则从链表2的头节点继续遍历,同样,如果N2先走完了链表2的尽头,则从链表1的头节点继续遍历,也就是说,N1和N2都会遍历链表1和链表2。

因为两个指针,同样的速度,走完同样长度(链表1+链表2),不管两条链表有无相同节点,都能够到达同时到达终点。

(N1最后肯定能到达链表2的终点,N2肯定能到达链表1的终点)。

所以,如何得到公共节点:

有公共节点的时候,N1和N2必会相遇,因为长度一样嘛,速度也一定,必会走到相同的地方的,所以当两者相等的时候,则会第一个公共的节点
无公共节点的时候,此时N1和N2则都会走到终点,那么他们此时都是null,所以也算是相等了。
下面看个动态图,可以更形象的表示这个过程~


class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* l1 = pHead1, *l2 = pHead2;
        while(l1 != l2){
            l1 = (l1==nullptr)?pHead2:l1->next;
            l2 = (l2==nullptr)?pHead1:l2->next;
        }
        return l1;
    }
};

标签:结点,遍历,链表,NC66,l1,N1,N2,节点
From: https://www.cnblogs.com/lihaoxiang/p/17962348

相关文章

  • 学生管理系统单链表
    #include"stdio.h"#include"stdlib.h"#include"string.h"#defineRD_NO(1<<0)#defineRD_NAME(1<<1)#defineRD_SEX(1<<2)#defineRD_SCORE(1<<3)//描述1个学生的属性structSTUDENT{......
  • 学生管理系统双链表
    #include"stdio.h"#include"stdlib.h"#include"string.h"#defineRD_NO(1<<0)#defineRD_NAME(1<<1)#defineRD_SEX(1<<2)#defineRD_SCORE(1<<3)//描述1个学生的属性structSTUDENT{......
  • 数据结构线性表之【循环链表、双向链表】
    循环链表在单链表中,每个结点都带有一个指向其后继结点的指针,但因为表尾元素没有后继结点,所以表尾结点的指针域为空,表明它不指向任何结点,并表示这个结点是最后一个结点。现在修改这个约定,将表尾结点的指针指回头结点,从而形成一类新链表。在这样的链表中,从任何一个结点出发并沿着指针......
  • 刷题笔记——单向链表(C++)
    206.反转链表-力扣(LeetCode)给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。解题思路三指针。temp指针用于存储当前节点的下一节点,pre指针用于存储当前节点反转后指向的新节点。具体操作如下:反转过程:代码实现classSolution{public:ListNode*reverseList(Li......
  • 循环单链表实现
    #include<stdio.h>#include<stdlib.h>#defineElemtypeint#defineERROR-1/*循环链表实现*/typedefstructNode{Elemtypee;Node*next;}Node,*LinkList;voidInitList(LinkList&pHead){pHead=(Node*)malloc(sizeof(Node)......
  • 链表-adlist
    2.链表相关文件adlist.hadlist.c1.定义typedefstructlistNode{structlistNode*prev;structlistNode*next;void*value;}listNode;typedefstructlistIter{listNode*next;intdirection;}listIter;typedefstructlist{l......
  • 数据结构【线性表之单链表】
    链表链表:线性表还可以使用链式存储方式保存,即线性表中的各个元素保存在各自的存储空间中,形成一个个节点。这些结点在内存的地址不要求是相邻的,它们之间通过指针连接起来。特点:灵活存储,不要求预先分配一块连续的空间,而是按需分配,随时需要,随时分配不要求分配的空间必须是相邻的没有......
  • 【C++】STL 容器 - list 双向链表容器 ② ( list 常用 api 简介 | 首尾 添加 / 删除
    文章目录一、元素操作1、首尾添加/删除元素2、获取首尾元素二、迭代器遍历容器1、正向迭代与反向迭代2、代码示例一、元素操作1、首尾添加/删除元素list双向链表容器提供了push_back、pop_back、push_front和pop_front等一系列用于操作列表元素的成员函数,函......
  • 【C++】STL 容器 - list 双向链表容器 ① ( 容器特点 | 容器操作时间复杂度 | 构造函
    文章目录一、list双向链表容器简介1、容器特点2、容器操作时间复杂度3、遍历访问5、头文件二、list双向链表容器构造函数1、默认无参构造函数2、创建包含n个相同元素的list双向链表3、使用初始化列表构造list双向链表4、使用另外一个list容器构造list双向链表容器......
  • 【C++】STL 容器 - list 双向链表容器 ③ ( list 常用 api 简介 | 中间位置 插入 / 删
    文章目录一、list双向链表容器的中间位置插入元素1、在指定位置插入1个元素-insert函数2、在指定位置插入n个相同元素-insert函数3、中间位置插入另一个容器的指定范围内的元素-insert函数二、list双向链表容器的中间位置删除元素1、删除容器中所有元素......