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

【题目】
输入两个链表，找出它们的第一个公共结点。
【思路】
链表特点：
两个单向链表由公共节点，那么这两个链表从给某一节点开始，他们的m_pNext都指向同一个节点，之后所有的节点都是重合的。
【题52】两个链表的第一个公共节点
方法一
蛮力法：第一个链表顺序遍历，没遍历一个节点，在第二个链表上顺序遍历，节点一样说明开始重合，———————————————————————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;
    }
}

【例】
【题52】两个链表的第一个公共节点
参考：
1.《剑指offer》

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

相关推荐