LeetCode Intersection of Two Linked Lists

LeetCode Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

 

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

给定两个链表,如果这两个链表在某个点相交,并且此后合并为一个链表,要找出这个交点;如果不想交,返回NULL。

简单的方法是,如果两个链表相交,比如题图在c1相交,则对于两个链表,从相交点往后长度是一样的,所以我们可以先求出两个链表的长度,假设长度差是delta,则较长链表先前进delta步,此时长短链表的往后的路都是一样长了,这样两个链表一起走,如果发现有相等的节点,则是相交节点,否则两个链表不相交。

本思路代码如下:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    	int len1 = 0, len2 = 0;
    	ListNode *h1 = headA, *h2 = headB;
    	while(h1){
    		++len1;
    		h1 = h1->next;
    	}
    	while(h2){
    		++len2;
    		h2 = h2->next;
    	}
    	h1 = headA;
    	h2 = headB;
    	if(len1 > len2){
    		while(len1 > len2){
    			h1 = h1->next;
    			--len1;
    		}
    	} else if(len2 > len1) {
    		while(len2 > len1){
    			h2 = h2->next;
    			--len2;
    		}
    	}
    	while(h1 && h2 && h1 != h2){
    		h1 = h1->next;
    		h2 = h2->next;
    	}
    	if(!h1 || !h2)return NULL;
    	else return h1;
    }
};

本代码提交AC,用时39MS。

还有一种思路很巧妙,参考:http://www.cnblogs.com/yuzhangcmu/p/4128794.html

具体是这样的,比如题目中的例子,假设指针pA和pB分别指向A,B两个链表,两个指针同时不断的一步一步走,当pA走到结尾时,pA指向B链表表头开始走,同理当pB走到结尾时,pB指向A链表表头开始走。不断的走,当pA和pB指向同一个节点时,就是那个相交的节点。这个很巧妙呀,当pA和pB走到相交点时,他们走过的路程其实是相等的,比如题目中,他们都走了9个节点后相遇了。

代码如下:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    	if(headA == NULL || headB == NULL) return NULL;
    	ListNode *h1 = headA, *h2 = headB;
    	ListNode *tail1 = NULL, *tail2 = NULL;
    	while(true){
    		if(h1 == NULL) h1 = headB;
    		if(h2 == NULL) h2 = headA;

    		if(h1->next == NULL) tail1 = h1;
			if(h2->next == NULL) tail2 = h2;

    		if(tail1 != NULL && tail2 != NULL && tail1 != tail2) return NULL;

    		if(h1 == h2) return h1;

    		h1 = h1->next;
    		h2 = h2->next;
    	}
    }
};

本代码提交AC,用时36MS。

Leave a Reply

Your email address will not be published. Required fields are marked *