两个链表的第一个公共节点

题目描述

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

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

思路一:蛮力法

顺序遍历第一个链表，每遍历一个节点就在第二个链表上顺序遍历每个节点，如果相同，则为公共节点。

时间复杂度：如果第一个链表的长度为m,第二个链表的长度为n,那么时间复杂度为o(mn)

思路二：辅助栈（空间换时间）

以上的两个链表的公共节点为6

由于题目是单链表，那么如果两个链表在某个公共节点重合，也就意味着他们的下一个节点也相同，即从公共节点开始到链表结束，都是重合的。

那么如果我们从链表的尾部开始比较，最后一个相同的节点就是我们要找的第一个公共节点。

那么如何实现从尾部开始比较呢？

由于这个是单向链表，我们不能从尾部开始向前遍历，所以我们需要一个辅助栈来实现“后入先出”的道理，即从尾部开始向前遍历。

我们采用两个辅助栈分别存储了两个链表，这样两个链表的尾节点就位于栈顶，我们依次比较栈顶的两个元素，如果相同就弹出栈顶继续比较下一个栈顶，直到找到最后一个相同的节点。

时间复杂度：o(m+n)

空间复杂度：O(m+n)

思路三

如果我们从头部来寻找第一个公共节点呢？

那么这里需要考虑到的问题就是两个链表的长度不一致导致到达公共节点的时间不同步，那么我们可以通过找到长的链表比短的链表多的长度，然后让长的链表先开始遍历多的长度，然后再同时遍历，直到公共节点

时间复杂度：O(m+n)

空间复杂度：0

import java.util.List;

public class CommonNode {

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int len1 = getLen(pHead1);
        int len2 = getLen(pHead2);

        int lenDif = len1 - len2;
        ListNode pHeadLong = pHead1;
        ListNode pHeadShort = pHead2;
        if(len1 < len2){
            pHeadLong = pHead2;
            pHeadShort = pHead1;
            lenDif = len2 - len1;
        }

        for(int i = 0;i < lenDif;i++){
            pHeadLong = pHeadLong.next;
        }

        while(pHeadLong != null && pHeadShort != null && pHeadLong != pHeadShort){
            pHeadLong = pHeadLong.next;
            pHeadShort = pHeadShort.next;
        }
        ListNode pCommonNode = pHeadLong;
        return pCommonNode;
    }


    public int getLen(ListNode pHead){
        int len = 0;
        while(pHead != null){
            len++;
            pHead = pHead.next;
        }
        return len;
    }



}

参考：

《剑指offer》