剑指offer--两个链表的第一个公共结点（java）

素颜马尾好姑娘i 2021-10-30 01:22 256阅读 0赞

### 剑指offer--两个链表的第一个公共结点 ###

两种常见解法：

1.  暴力查找法，两层循环，第一层遍历一条链，镶嵌的遍历的是另一条，查找相同的那一块。  
    **时间复杂度：O(n^2)**
    
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { 
        	ListNode pHead2Temp = pHead2;
        	while((pHead1!= null)) { 
        		while((pHead2Temp!=null)) { 
            		if(pHead1.equals(pHead2Temp))
            			return pHead1;
            		pHead2Temp = pHead2Temp.next;
        		}
        		pHead1 = pHead1.next;
        		pHead2Temp = pHead2;
        	}
        	return null;
        }

2.去掉长链多出来的那部分，然后同时遍历两个链表，一定能找到  
**时间复杂度：O(n)**

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { 
        	if(pHead1 == null || pHead2 == null)
        		return null;
        	int len1 = GetLen(pHead1);
        	int len2 = GetLen(pHead2);
        	int cha = len1-len2;
        	ListNode LongList = pHead1;
        	ListNode ShortList = pHead2;
        	if(len1<len2) { 
        		LongList = pHead2;
        		ShortList = pHead1;
        		cha = len2-len1;
        	}
        	for(int i=0;i<cha;i++) { 
        		LongList = LongList.next;
        	}
        	while((LongList!=null) && (ShortList!=null)) { 
        		if(LongList.equals(ShortList))
        			return LongList;
        		LongList = LongList.next;
        		ShortList = ShortList.next;
        	}
    		return null;
        }
    
    	private int GetLen(ListNode pHead1) { 
    		int len = 0;
    		while(pHead1!= null) { 
    			len++;
    			pHead1 = pHead1.next;
    		}
    		return len;
    	}