首页 > 其他分享 >相交链表

相交链表

时间:2024-10-31 19:32:09浏览次数:1  
标签:结点 cur2 cur1 相交 链表 curA ListNode

两个链表的第一个公共结点(相交链表)

题目链接:牛客 || LeetCode 160
描述
输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)
例如,输入{1,2,3},{4,5},{6,7}时,两个无环的单向链表的结构如下图所示:
在这里插入图片描述
可以看到它们的第一个公共结点的结点值为6,所以返回结点值为6的结点。
示例:

输入:{1,2,3},{4,5},{6,7}
返回值:{6,7}
说明:第一个参数{1,2,3}代表是第一个链表非公共部分,第二个参数{4,5}代表是第二个链表非公共部分,最后的{6,7}表示的是2个链表的公共部分,这3个参数最后在后台会组装成为2个两个无环的单链表,且是有公共节点的

思路:

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

代码实现:

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while(cur1 != cur2){
            if (cur1 == null) cur1 = pHead2;
            else              cur1 = cur1.next;
            if (cur2 == null) cur2 = pHead1;
            else              cur2 = cur2.next;
        }
        return cur1;
    }
}

使用三元运算符

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        while( curA != curB ){
            curA = curA == null ? headB : curA.next;
            curB = curB == null ? headA : curB.next;
        }
        return curA;
    }
}

标签:结点,cur2,cur1,相交,链表,curA,ListNode
From: https://www.cnblogs.com/dwhere/p/18518719

相关文章

  • 代码随想录之链表刷题总结
    目录1.链表理论基础2.移除链表元素3.设计链表4.翻转链表5.两两交换链表中的节点6.删除链表中的第N个节点7.链表相交8.环形链表1.链表理论基础链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后......
  • 《链表篇》---两两交换链表中的节点(中等)
    题目传送门1.定义一个虚拟节点链接链表2.定义一个当前节点指向虚拟节点3.在当前节点的下一个节点和下下一个节点都不为null的情况下。定义node1和node2。保存当前节点后面两个节点的地址。cur.next=node2;node1.next=node2.next;node2.next=node1;cur=node1;4.......
  • 《链表篇》---删除链表的倒数第N个节点(中等)
    题目传送门 方法一:计算链表长度(迭代)1.计算链表长度,并且定义哑节点链接链表。2.从哑节点开始前进length-n次。即为被删除节点的前置节点。3.进行删除操作。4.返回哑节点的后置节点classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){......
  • DAY49 ||1143.最长公共子序列| 1035.不相交的线 | 53. 最大子序和 |392.判断子序列
    1143.最长公共子序列题目:1143.最长公共子序列-力扣(LeetCode)给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的......
  • 单链表题带刷(二)
    目录一、链表的回文结构1.1题目1.2解题思路二、相交链表2.1题目一、链表的回文结构1.1题目https://www.nowcoder.com/share/jump/6870342311730273670970https://www.nowcoder.com/share/jump/68703423117302736709701.2解题思路思路一:创建新链表,将原链表反......
  • C语言判断单链表是否相交
    ////CreatedbyAdministratoron2024/10/29.//#ifndefLINK_H#defineLINK_H/***链表的结构体*/typedefstructLink{intelement;structLink*next;}link;#endif//LINK_H////判断单链表是否相交//CreatedbyAdministratoron2024/10/30......
  • C语言链表
    ////CreatedbyAdministratoron2024/10/29.//#ifndefLINK_H#defineLINK_H/***链表的结构体*/typedefstructLink{intelement;structLink*next;}link;#endif//LINK_H////链表//CreatedbyAdministratoron2024/10/28.//#pragmao......
  • C语言链表反转的四种方法
    ////CreatedbyAdministratoron2024/10/29.//#ifndefLINK_H#defineLINK_H/***链表的结构体*/typedefstructLink{intelement;structLink*next;}link;#endif//LINK_H////四种链表反转算法//CreatedbyAdministratoron2024/10/29.......
  • 复杂度分析,数据结构的数组与链表
    复杂度分析,数据结构的数组与链表参考书籍:Hello算法目录复杂度分析,数据结构的数组与链表复杂度分析时间复杂度空间复杂度数据结构数组与链表数组链表列表复杂度分析复杂度分析是用来判断一个算法效率的手段,执行时所需的时间和空间资源则是正好对应时间和空间复杂度。考虑到执......
  • 线性表-单链表c语言实现
    一、基本介绍    回顾单链表的知识二、单链表#include<stdio.h> #include<cstdlib>typedefintElemType;typedefintStatus; #defineERROR0#defineOK1#defineOVERFLOW-2#defineNULL0//定义单链表中结点类型 typedefstructLNode{  ......