【题52】两个链表的第一个公共节点

╰半夏微凉° 2022-03-06 13:35 147阅读 0赞

【题目】  
输入两个链表，找出它们的第一个公共结点。  
【思路】  
链表特点：  
两个单向链表由公共节点，那么这两个链表从给某一节点开始，他们的m\_pNext都指向同一个节点，之后所有的节点都是重合的。  
![在这里插入图片描述][20190319090605714.png]  
**方法一**  
蛮力法：第一个链表顺序遍历，没遍历一个节点，在第二个链表上顺序遍历，节点一样说明开始重合，———————————————————————O（mn）  
**方法二**  
辅助栈：如果有公共节点，那么公共节点出现在尾部，从尾部往前比较，到最后一个相同的就是我们要找的节点。如图 遍历7，6。先进后出的特点，使用一个两个辅助栈，分别遍历两个链表放入栈中。比较栈中的节点，相同把栈顶弹出接着比较，直到找到最后一个相同的节点。  
**方法三**  
简单的方法：首先遍历两个链表长度为m，n找到较长的链表（若m=5>n=4）,则让长度为m的链先走m-n步，再同时走同时比较。如图，让上面的链表先走5-4=1步，再一起走，2！=4，3！=5，6=6.  
【实现】

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        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++;//链表1长度
            }
            int count2 = 0;
            ListNode p2 = pHead2;
            while(p2 != null){
                p2 = p2.next;
                count2++;//链表2长度
            }
            int flag = count1 -count2;//表1 表2差值
            if(flag > 0){//如果表1 比表2长
                while(flag>0){
                    pHead1 = pHead1.next;
                    flag--;
                }
                while(pHead1 != pHead2){//两个节点不同
                    pHead1 = pHead1.next;
                    pHead2 = pHead2.next;
                }
                return pHead1;
            }
            if(flag <= 0){//表1不比表2 长
                while(flag<0){
                    pHead2 = pHead2.next;
                    flag++;
                }
                while(pHead1 != pHead2){
                    pHead1 = pHead1.next;
                    pHead2 = pHead2.next;
                }
                return pHead1;
            }
            return null;
        }
    }

【例】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
参考：  
1.《剑指offer》

[20190319090605714.png]: /images/20220303/bcd230821ee74f67866d062aa3170d3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220303/8f0afcecb0614d77b7442779b354497f.png