C++版 - 剑指offer之面试题37：两个链表的第一个公共结点[LeetCode 160] 解题报告
C++版 - 剑指offer之面试题37：两个链表的第一个公共结点[LeetCode 160] 解题报告
Enjoy233
发布于 2019-03-05 14:42:18
发布于 2019-03-05 14:42:18
剑指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 → b3begin 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.
- If the two linked lists have no intersection at all, return
#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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016年07月06日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读