题目描述

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

解题思路

暴力解法：

第一步，分别求出链表1和2的长度。
第二步，依据差距挪动指针。
第三步，寻找公共子节点

优化解法：使用HashSet不可重复的性质，发现重复节点（值相同且next相同）即可返回。

代码

/** * */
package 链表;

import java.util.HashSet;
import java.util.TreeSet;

/** * <p> * Title:FindFirstCommonNode * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月22日 下午4:52:12 */
public class FindFirstCommonNode {
    public ListNode NodeFindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        // 第一步，分别求出链表1和2的长度
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        int len1 = findListLenth(pHead1);
        int len2 = findListLenth(pHead2);
        // 第二步，依据差距挪动指针
        if (len1 > len2) {
            p1 = walkStep(pHead1, len1 - len2);
        } else {
            p2 = walkStep(pHead2, len2 - len1);
        }
        // 第三步，寻找公共子节点
        while (p1 != null && p2 != null) {
            if (p1 == p2) {
                return p1;
            }
            p1 = p1.next;
            p2 = p2.next;

        }
        return null;

    }

    // 移动步数的函数
    public ListNode walkStep(ListNode pHead1, int step) {
        ListNode p = pHead1;
        for (int i = 0; i < step; i++) {
            p = p.next;
        }
        return p;
    }

    // 计算长度的函数
    public int findListLenth(ListNode node) {
        if (node == null)
            return 0;
        int sum = 1;
        ListNode p = node;
        while (p.next != null) {
            p = p.next;
            sum++;
        }
        return sum;
    }

    // ================================================================================优化
    public ListNode NodeFindFirstCommonNodeSuper(ListNode pHead1,
            ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        HashSet<ListNode> set = new HashSet<ListNode>();
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (p1 != null) {
            set.add(p1);
            p1 = p1.next;
        }
        while (p2 != null) {
            if (set.contains(p2)) {
                return p2;
            }
            p2 = p2.next;
        }
        return null;

    }
}