剑指offer之面试题37 两个链表的第一个公共结点


提交网址： http://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189

leetcode 160: https://leetcode.com/problems/intersection-of-two-linked-lists/


参与人数：3252   时间限制：1秒   空间限制：32768K


本题知识点： 链表 时间空间效率的平衡

题目描述

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


分析：

方法1：

使用两个辅助栈，从尾部往头部找最后一个共同节点。但这种方法空间复杂度较高，时间复杂度为O(m+n)。


方法2：

先分别遍历两个链表，取各自的长度。较长的链表中的头指针一直往后面走，直到遇到相同节点。时间复杂度为O(m+n)。


#include <iostream>
using namespace std;

struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
};
 
class Solution {
public:
	int getLen(ListNode *head)
	{
		int count=0;
		ListNode *p=head;
		while(p != NULL)
		{
			count++;
			p=p->next;
		}
		return count;		
	}
	
    ListNode* FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2) {
        if(pHead1==NULL || pHead2==NULL) return NULL;
        int len1=getLen(pHead1);
        int len2=getLen(pHead2);
        
        if(len1 >= len2)
        {
        	int gap=len1-len2;
        	while(gap--) pHead1=pHead1->next;
		}
		else {
        	int gap=len2-len1;
        	while(gap--) pHead2=pHead2->next;			
		}
		while(pHead1 != pHead2)
		{
			pHead1=pHead1->next;
			pHead2=pHead2->next;
		}
        return pHead1;
    }
};

// 以下为测试部分
int main()
{
	ListNode *pA=new ListNode(1);
	ListNode *p1=new ListNode(2);
	ListNode *p2=new ListNode(3);
	ListNode *pB=new ListNode(4);	
	ListNode *p3=new ListNode(5);		
	ListNode *p4=new ListNode(6);
	ListNode *p5=new ListNode(7);
	
	pA->next=p1;
	p1->next=p2;
	p2->next=p4;
	pB->next=p3;
	p3->next=p4;
	p4->next=p5;
	p5->next=NULL;	

	Solution sol;
	
	ListNode *pOut=sol.FindFirstCommonNode(pA,pB);
	
	cout<<pOut->val<<endl;
	return 0;
}



LeetCode 160 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.


#include <iostream>
using namespace std;
struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
}; 
class Solution {
public:
	int getLen(ListNode *head)
	{
		int count=0;
		ListNode *p=head;
		while(p != NULL)
		{
			count++;
			p=p->next;
		}
		return count;		
	}	
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

        if(headA==NULL || headB==NULL) return NULL;
        int len1=getLen(headA);
        int len2=getLen(headB);
        
        if(len1 >= len2)
        {
        	int gap=len1-len2;
        	while(gap--) headA=headA->next;
		}
		else {
        	int gap=len2-len1;
        	while(gap--) headB=headB->next;			
		}
		while(headA != headB)
		{
			headA=headA->next;
			headB=headB->next;
		}
        return headA;
    }
};

// 以下为测试部分
int main()
{
	ListNode *pA=new ListNode(1);
	ListNode *p1=new ListNode(2);
	ListNode *p2=new ListNode(3);
	ListNode *pB=new ListNode(4);	
	ListNode *p3=new ListNode(5);		
	ListNode *p4=new ListNode(6);
	ListNode *p5=new ListNode(7);	
	pA->next=p1;
	p1->next=p2;
	p2->next=p4;
	pB->next=p3;
	p3->next=p4;
	p4->next=p5;
	p5->next=NULL;
	Solution sol;	
	ListNode *pOut=sol.getIntersectionNode(pA,pB);	
	cout<<pOut->val<<endl;
	return 0;
}