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.
分析:题意即为寻找两个单链表相交开始的节点
如果我们直接通过遍历两个链表来寻找交叉元点
代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL || headB==NULL) return NULL;
ListNode *result=NULL;
while(headB){
if(headA && headA->val == headB->val) {
result = headA;
}
while (headA)
{
if (headA->next && headA->next->val == headB->val) {
result=headA->next;
}
headA = headA->next;
}
if(headB->next) headB= headB->next;
} return result;
}
};
会出现超时:Time Limit Exceeded
看来还是得认真审题加分析,找到解题的关键特征来提高效率。(一个星期没刷题就变得头脑简单了)
最简单的代码是这样子滴:
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { while (headA && headB) {
if (headA->val < headB->val)
headA = headA->next;
else if (headA->val > headB->val)
headB = headB->next;
else if (headA->val == headB->val)
return headA;
}
return nullptr;
}
};
当然也可以是这样的思路:
我们可以遍历两个链表得到各自的长度,然后将长度更长的链表向前移动,使两个链表进行对齐,之后一起遍历,直到找到第一个相同的节点。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { auto currA = headA, currB = headB;
int countA = 0, countB = 0; while (currA) {
currA = currA->next, countA++;
}
while (currB) {
currB = currB->next, countB++;
}
int diff = std::abs(countA - countB);
if (countB > countA) { swap(headA, headB); }
while (diff--) {
headA = headA->next;
}
while (headA != headB) {
headA = headA->next, headB = headB->next;
}
return headA;
}
};
或者:
为了节省计算,在计算链表长度的时候,顺便比较一下两个链表的尾节点是否一样,若不一样,则不可能相交,直接可以返回NULL
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == NULL || headB == NULL)
return NULL;
ListNode* iter1 = headA;
ListNode* iter2 = headB;
int len1 = 1;
while(iter1->next != NULL)
{
iter1 = iter1->next;
len1 ++;
}
int len2 = 1;
while(iter2->next != NULL)
{
iter2 = iter2->next;
len2 ++;
}
if(iter1 != iter2)
return NULL;
if(len1 > len2)
{
for(int i = 0; i < len1-len2; i ++)
headA = headA->next;
}
else if(len2 > len1)
{
for(int i = 0; i < len2-len1; i ++)
headB = headB->next;
}
while(headA != headB)
{
headA = headA->next;
headB = headB->next;
}
return headA;
}
};
最新文章
- .Net多线程编程—任务Task
- [game]十字链表的AOI算法实现
- MFC中的各种DC区别
- 新手选择使用 Linux 桌面的七个注意点
- activitydialog
- 对web日志文件实现按照人员、行为分类
- (ASP.NET)C#连接Oracle数据库示例(中文乱码问题解决)
- HTML5 基础
- c++primerplus(第六版)编程题&mdash;&mdash;第3章(数据类型)
- poj3254:基础状压dp
- ADO.Net总结
- Scrapy入门程序点评
- [C#参考]锁定lock
- secache 详解
- UWP 手绘视频创作工具技术分享系列 - 位图的绘制
- 企业信息化快速开发平台--JeeSite
- 运行Applet程序
- Connection 对象简介 方法解读 JDBC简介(四)
- codeforces 786E ALT
- [批处理]使用IncrediBuilder加速自动化测试过程