剑指Offer | 两个链表的第一个公共结点

谁借莪１个温暖的怀抱￠ 2022-05-23 05:49 139阅读 0赞

## 一、题目 ##

输入两个链表，找出它们的第一个公共结点。

## 二、思路 ##

(1) 两个链表是单向链表，如果两个链表有公共节点，那么这两个链表从某一节点开始，它们的Next都指向同一个节点，之后它们所有的节点都是重合的，不可能再出现分叉。所以拓扑形状看起来是Y型。  
![这里写图片描述][70]  
(2)  
首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。  
在第二次遍历的时候，先在较长的节点上走若干步，接着同时在两个链表上遍历，找到的第一个相同的节点就是它们的公共的节点。该算法的时间复杂度为：O(m+n)。

## 三、代码 ##

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            if(pHead1 == null || pHead2 == null){
                return null;
            }
            //数第一个链表长度
            int count1 = 0;
            ListNode p1 = pHead1;
            while(p1 != null){
                p1 = p1.next;
                count1++;
            }
            //数第二个链表长度
            int count2 = 0;
            ListNode p2 = pHead2;
            while(p2 != null){
                p2 = p2.next;
                count2++;
            }
            int flag = count1 - count2;
            //当第一个链表较长时
            if(flag > 0){
                while(flag > 0){
                    pHead1 = pHead1.next;
                    flag--;
                }
                while(pHead1 != pHead2){
                    pHead1 = pHead1.next;
                    pHead2 = pHead2.next;
                }
                return pHead1;
            }else{
                while(flag > 0){
                    pHead2 = pHead2.next;
                    flag--;
                }
                while(pHead1 != pHead2){
                    pHead1 = pHead1.next;
                    pHead2 = pHead2.next;
                }
                return pHead1;
            }
        }

[70]: /images/20220523/f74f20a5b6814f5abd733cc8d8a668a0.png