找到两个链表的第一个公共节点 37--剑指offer

可以发现两个链表在第一个节点重合之后不会再分开了

简单多说一句不会分开的原因，因为单向链表的节点只有一个nextNode指向下一个节点，那么如果该节点重合了，那么后面的节点一定是同一个。

一般这种问题要用两个类似指针的东西，一个先走，一个后走

所以我们先遍历找到两个链表的长度m和n，如果m大，m比n大多少，比如说k，那么先让m先走k步，然后n和m再一起走。

class ListNode {
    int val;
    ListNode next;

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

public class Main {
    public int getLength(ListNode head) {
        int count = 0;
        if (head == null) {
            return 0;
        }
        while (head != null) {
            count++;
            head = head.next;
        }
        return count;
    }//getLength

    public  ListNode findFirstCommonNode(ListNode headNode1, ListNode headNode2) {
        ListNode resultNode = null;
        int length1 = getLength(headNode1);
        int length2 = getLength(headNode2);
        ListNode LongListNode;
        ListNode ShortListNode;
        int steps = 0;
        if (length1 > length2) {
            LongListNode = headNode1;
            ShortListNode = headNode2;
            steps = length1 - length2;
        } else {
            LongListNode = headNode2;
            ShortListNode = headNode1;
            steps = length2 - length1;
        }
        for (int i = 0; i < steps; i++) {
            LongListNode = LongListNode.next;
        }
        while (LongListNode != null && ShortListNode != null && LongListNode.val != ShortListNode.val) {
            LongListNode = LongListNode.next;
            ShortListNode = ShortListNode.next;
        }
        resultNode = LongListNode;
        return resultNode;
    }//findFirstCommonNode

    public static void main(String[] args) {
        ListNode headNode1 = new ListNode(1);
        headNode1.next = new ListNode(2);
        headNode1.next.next = new ListNode(3);
        headNode1.next.next.next = new ListNode(6);
        headNode1.next.next.next.next = new ListNode(7);
        ListNode headNode2 = new ListNode(4);
        headNode2.next = new ListNode(5);
        headNode2.next.next = new ListNode(6);
        headNode2.next.next.next = new ListNode(7);
        System.out.println(new Main().findFirstCommonNode(headNode1,headNode2).val);//6
    }
}