首页 > 其他 > 详细

Intersection of Two Linked Lists

时间:2015-03-31 22:18:53      阅读:148      评论:0      收藏:0      [点我收藏+]

题目: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.

示例代码如下:
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		if(headA==NULL ||headB==NULL)
			return NULL;
		int lenHeadA=0,lenHeadB=0;
		ListNode *p=headA,*q=headB;
		//求链表headA和headB的长度
		while(p){
			p=p->next;
			lenHeadA++;
		}
		p=headA;
		while(q){
			q=q->next;
			lenHeadB++;
		}
		q=headB;
		int distance=0;
		if(lenHeadA>lenHeadB){
			distance=lenHeadA-lenHeadB;
			for(int i=0;i<distance;i++)
				p=p->next;
		}
		if(lenHeadA<lenHeadB){
			distance=lenHeadB-lenHeadA;
			for(int i=0;i<distance;i++)
				q=q->next;
		}
		//循环结束的条件是p==q!=null(有相交点) 
		//或者是p==q==null(无相交点)
		while(p!=q){
			p=p->next;
			q=q->next;
		}
		return p;
};


Intersection of Two Linked Lists

原文:http://blog.csdn.net/sxhlovehmm/article/details/44785783

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!