本文共 2547 字，大约阅读时间需要 8 分钟。

题目链接：

题目描述：输入两个链表，找出它们的第一个公共节点。 如上所示，链表A和B在c1开始相交。这里看到不少人有个问题，说两个链表第一个相交节点之后的部分不一定相同。这里我觉得可能他们都没弄清楚什么是链表，这里我简单说一下，我们都知道链表是由一些节点组成的非连续存储结构，既然连续，那么怎么找下一个节点呢，自然就是指针了，因此每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。所以只要找到两个链表相交第一个节点，必然后面都是相同的。

话不多说，来看一组样例：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

思路：提供两种做法。

法一：先遍历两个链表取得两链表长度，假设为lenA和lenB，然后让长的链表先跑到fabs(lenA-lenB)次，这时候两个链表就等长了，接下来就直接同步移动找公共节点即可。 代码：

/** * 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) {
           if(headB==null||headA==null) return null;         int lenA=getLength(headA);        int lenB=getLength(headB);        int len=lenA-lenB;        ListNode longList=headA;//默认A长        ListNode shortList=headB;        if(lenA
   
    0) longList=longList.next;        while(longList!=null){
               if(longList==shortList) return longList;            longList=longList.next;            shortList=shortList.next;        }        return null;    }    public int getLength(ListNode node){
           int len=0;        ListNode cur=node;        while(cur!=null){
               len++;            cur=cur.next;        }        return len;    }}
   

法二：采用链表拼接的方法，将链表A拼接到B尾部，将链表B拼接到链表A尾部，这时候两个链表就可以同步移动判断相交了。but！！！注意：我们这里所说的拼接只是逻辑上的拼接，什么意思，也就是我们采用的一种思想，实际处理当然不可能直接拼接，因此两个链表同步移动，当A移动到末尾时候，将指向A的链表指针指向链表B的头节点，实现了A-B 所谓的拼接，同样，当B移动到末尾的时候，将指向B的链表指针指向A的头节点，这样实现了B-A 的拼接。最后需要判断一下是否两个链表没有相交节点，也就是当实现了A-B和B-A拼接一次之后，还没能找到公共节点，那么这两个链表必然没有公共节点。

代码：

/** * 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) {
           if(headB==null||headA==null) return null;         ListNode p=headA;        ListNode q=headB;        int flag=0;        while(p!=q){
               p=p.next;            q=q.next;            if(p==null){
                   p=headB;                flag++;            }            if(q==null){
                   q=headA;                flag++;            }            if(flag>2) return null;        }        return p;    }}

转载地址：https://dh-butterfly.blog.csdn.net/article/details/108441190 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！