两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点（保证一定存在公共结点）

解题思路

假设两个链表结构如图所示，最简单的想法就是：让长的链表先走，走完两个链表的长度差，然后再一起走

public class Solution {
    
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        
        if(pHead1 == null || pHead2 == null) {
            return null;
        }
        
        int length1 = getLength(pHead1);
        int length2 = getLength(pHead2);
        
        ListNode curNode1 = pHead1;
        ListNode curNode2 = pHead2;
        
        if(length1 >= length2) {
            int len = length1 - length2;
            while(len > 0) {
                curNode1 = curNode1.next;
                len--;
            }
        }
        
        if(length2 > length1) {
            int len = length2 - length1;
            while(len > 0) {
                curNode2 = curNode2.next;
                len--;
            }
        }
        
        while(curNode1 != curNode2) {
            curNode1 = curNode1.next;
            curNode2 = curNode2.next;
        }
        
        return curNode1;
    }
    
    public int getLength(ListNode pHead) {
        int count = 0;
        ListNode curNode = pHead;
        while(curNode != null) {
            count++;
            curNode = curNode.next;
        }
        return count;
    }
}

上一种做法使用了差值来让链表长度相同，也可以用别的方法。假设链表 A 长度为 a， 链表 B 的长度为 b，此时 a != b，但是，a + b == b + a

public class Solution {
    
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode curNode1 = pHead1;
        ListNode curNode2 = pHead2;
        while(curNode1 != curNode2) {
            curNode1 = curNode1 == null ? pHead2 : curNode1.next;
            curNode2 = curNode2 == null ? pHead1 : curNode2.next;
        }
        return curNode1;
    }
}

也可以运用 HashMap 的特性帮助解题

import java.util.HashMap;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode curNode1 = pHead1;
        ListNode curNode2 = pHead2;
        HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
        while (curNode1 != null) {
            hashMap.put(curNode1, null);
            curNode1 = curNode1.next;
        }
        while (curNode2 != null) {
            if (hashMap.containsKey(curNode2))
                return curNode2;
            curNode2 = curNode2.next;
        }
        return null;
    }
}