【剑指Offer】两个链表的第一个公共结点

题目

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

实现

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

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

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    int firstLen = getListLength(pHead1);
    int secondLen = getListLength(pHead2);
    int diff = firstLen - secondLen;

    if (diff > 0)
        pHead1 = findFirstNodeHelper(pHead1, diff);
    else if (diff < 0)
        pHead2 = findFirstNodeHelper(pHead2, -diff);

    while (pHead1 != null && pHead2 != null && pHead1 != pHead2) {
        pHead1 = pHead1.next;
        pHead2 = pHead2.next;
    }

    return pHead1;
}

private int getListLength(ListNode head) {
    int count = 0;

    while (head != null) {
        count++;
        head = head.next;
    }

    return count;
}

private ListNode findFirstNodeHelper(ListNode head, int step) {
    while (step != 0) {
        step--;
        head = head.next;
    }

    return head;
}