C++版 - 剑指offer之面试题37:两个链表的第一个公共结点[LeetCode 160] 解题报告

剑指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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券