题解 | #两个链表的第一个公共结点#

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int len1 = getListNodeLength(pHead1);
        int len2 = getListNodeLength(pHead2);
        int commonlength = Math.min(len1,len2);
        ListNode l1 = FindKthToTail(pHead1,commonlength);
        ListNode l2 = FindKthToTail(pHead2,commonlength);
        while(l1 != l2){
            l1 = l1.next;
            l2 = l2.next;
        }
        return l1;
    }

    public int getListNodeLength(ListNode pHead) {
        int len = 0;
        ListNode l1 = pHead;
        while(l1 != null){
            len++;
            l1 = l1.next;
        }
        return len;
    }

    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        int count = 1;
        ListNode pre = pHead;
        ListNode back = pHead;
        ListNode kong = null;
        if(pHead == null){
            return kong;
        }
        while(pre.next != null){
            if(count < k){
                pre = pre.next;
                count++;
            }else{
                pre = pre.next;
                back = back.next;
            }
        }
        if(count != k){
            return kong;
        }
        return back;
    }
}

思路:

1.获取两个链表的长度

2.获取两个长度的最小值commonlength,这样的话就是链表的公共长度

3.定义两个指针指向倒数第commonlength个位置,然后两个指针一起往后面移动,直到指向相同的节点