找到两个链表的第一个公共节点 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 != ShortListNode) {
            LongListNode = LongListNode.next;
            ShortListNode = ShortListNode.next;
        }
        resultNode = LongListNode;
        return resultNode;
    }//findFirstCommonNode

    public static void main(String[] args) {
        ListNode head1=new ListNode(1);
        ListNode second1=new ListNode(2);
        ListNode third1=new ListNode(3);
        ListNode forth1=new ListNode(6);
        ListNode fifth1=new ListNode(7);
        ListNode head2=new ListNode(4);
        ListNode second2=new ListNode(5);
//        ListNode third2=new ListNode(6);
//        ListNode forth2=new ListNode(7);
        head1.next=second1;
        second1.next=third1;
        third1.next=forth1;
        forth1.next=fifth1;
        head2.next=second2;
        second2.next=forth1;//直接指向forth1即可
        System.out.println(new Main().findFirstCommonNode(head1,head2).val);//6
    }
}