[数据结构与算法] 两个链表的第一个公共节点—

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 两个链表的第一个公共节点——LeetCode -> 正文阅读

[数据结构与算法]两个链表的第一个公共节点——LeetCode

力扣第 52题两个链表的第一个公共节点

在这里插入图片描述

力扣题目描述

在这里插入图片描述

示例

在这里插入图片描述

读懂题意

这一道力扣题属于简单类型，读起题目也是很容易的，题目给的意思是开头是两个链表，结尾可能两链表会相遇，就是能找到两链表的公共部位，题目的要求就是我们必须找到公共结点的位置，并且返回。由示例一可以看出，值相等并非一定是公共结点。但是公共结点的值一定是相等的，所以我们只能从结点出发，判断链链表指向是否为同一结点。如果在链尾之前能找到公共结点，就返回公共结点，如果没有找到就返回为null。

解题思路

首先最简单最容易理解的一个思路，双层while循环，判断A链表当前结点与链表B结点是否相等，不相等A就往下一个结点移动，B接着判断，一直移到最后一个节点。因为两链表的长度不一定相等，所以移动的距离也不同，采用双层循环来处理！

解题代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       ListNode a = headA;//获取A链表
       ListNode b = headB;//获取B链表
       while(a!=null){//如果A链表还没有走到最后一个结点
            b = headB;//每次从B链表的开头开始去遍历
           while(b!=null){//如果B还没有走到最后
               if(b==a){//如果找到则返回
                   return b;
               }
               b=b.next; //下一个B结点
           }
           a = a.next;//下一个A节点
       }
       return null;
    }
}