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

题目描述

输入两个链表，找出它们的第一个公共结点。如果有公共结点，则输出它们的第一个公共结点；如果没有公共结点，则输出null即可。

链表的定义

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

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

思路

有公共结点的情况：

这个时候就计算出pHead1链表的长度，pHead2链表的长度，然后让长的链表先走它们之间长度的差值，然后pHead1和pHead2同时走，必定同时遇到（此时就是公共结点）。

无公共结点的情况：

这个时候也是采取跟有公共结点一样的思路，让链表长的先走它们长度的差值步数，然后让他们同时走，这个时候同时走到null，返回null即可。

代码

package nowcoder;

/**
 * @author god-jiang
 * @date 2020/2/10  11:02
 */
public class FindFirstCommonNode {
    //链表的定义
    public class ListNode {
        int val;
        ListNode next = null;

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

    public ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        int length1 = 0;
        int length2 = 0;
        ListNode node1 = pHead1;
        ListNode node2 = pHead2;
        //计算出链表pHead1和pHead2的长度
        while (node1 != null) {
            length1++;
            node1 = node1.next;
        }
        while (node2 != null) {
            length2++;
            node2 = node2.next;
        }
        //让长的链表先走N步（N=Math.abs(length1-length2)）
        if (length1 > length2) {
            int go = length1 - length2;
            while (go > 0) {
                go--;
                pHead1 = pHead1.next;
            }
        } else {
            int go = length2 - length1;
            while (go > 0) {
                go--;
                pHead2 = pHead2.next;
            }
        }
        //同时走，只要有公共结点就会遇到，没有公共结点就返回null
        while (pHead1 != pHead2) {
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return pHead1;
    }
}