剑指Offer_36

题目

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

解题思路

一个简单的方法是：首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第二次遍历的时候，先在较长的节点上走若干步，接着同时在两个链表上遍历，找到的第一个相同的节点就是它们的公共的节点。该算法的时间复杂度为：O(m+n)。

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    private ListNode skipKNode(ListNode list, int k){
        while(k-- != 0){
            list = list.next;
        }
        return list;
    }
    
    private int length(ListNode pHead){
        int cnt = 0;
        while(pHead != null){
            ++cnt;
            pHead = pHead.next;
        }
        return cnt;
    }
    
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    	if(pHead1 == null || pHead2 == null){
            return null;
        }
        int len1 = length(pHead1);
        int len2 = length(pHead2);
        int k = Math.abs(len1-len2);
        
        if(len1 > len2){
        //java参数传值，当参数为对象时，传递是对象引用的拷贝
        //传递给skipKNode的参数是pHead1引用的一个拷贝
        //如果pHead1在skipKNode中发生改变，那么两个形参和实参会引用不同的地址值
            pHead1 = skipKNode(pHead1, k);
        }
        else{
            pHead2 = skipKNode(pHead2, k);
        }
        
        while(pHead1 != null && pHead2 != null){
            if(pHead1 == pHead2){
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }
}