《剑指offer第二版》面试题52：两个链表的第一个公共节点（java）

题目描述

• 输入两个链表，找出他们的第一个公共节点。

解题思路

1. 计算出两个链表的长度。并得到长度差diff。
2. 较长的链表先走diif个节点。此时两个链表剩余的长度是一样的。
3. 两个链表同时进行遍历，遇到第一个相同的节点，则返回。

代码

ListNode findFirstCommonNode(ListNode head1, ListNode head2){
    if (head1 == null || head1 == null) {
        return null;
    }
    int head1Length = 0;
    int head2Length = 0;

    ListNode node1 = head1;
    ListNode node2 = head2;
    // 计算链表长度
    while (node1 != null ) {
        node1 = node1.next;
        head1Length ++;
    }
    while (node2 != null ) {
        node2 = node2.next;
        head2Length ++;
    }

    ListNode nodeLong = head1;
    ListNode nodeShort = head2;
    int diff = head1Length - head2Length;
    if (head1Length < head2Length) {
        nodeLong = head2;
        nodeShort = head1;
        diff = head2Length - head1Length;
    }

    for (int i = 0; i < diff; i++) {
        nodeLong = nodeLong.next;
    }

    while (nodeLong != null && nodeShort!=null) {
        if (nodeLong == nodeShort) {
            return nodeLong;
        }
        nodeLong = nodeLong.next;
        nodeShort = nodeShort.next;
    }
    return null;
}