题目：
image.png
image.png
思路一：
可以使用c++自带的stl库中的set集合来进行查找
知识补充:
stl中set的使用： 其实set就是一个存放数据的集合，但是配备了一些很方便的操作 其中主要要用到的操作有三个: insert():插入元素 find():查找元素,返回给定值值得定位器，如果没找到则返回end()。 end():返回集合的尾迭代器，众所周知，STL 中区间都是左闭右开的，那么 end() 函数返回的迭代器即为指向集合中最大元素的下一个位置的迭代器，因此 --s.end() 才是指向集合中最大元素的迭代器，时间复杂度为 O(1)
具体的使用:
image.png
由此,可以得到大致思路:
1.遍历链表A,将A中节点对应的指针(地址),插入set
2.遍历链表B,将B中节点对应的指针(地址),到set中查找,发现set的第一个节点地址,就是两个链表的交点
如图:
image.png
思路一代码
/**
* 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) {
//std为命名空间,c++中的库其函数都存于std命名空间中(一种规范)
//set是stl库的一个集合类型,实际上是使用了红黑树数据结构进行封装
//(插入和删除的效率比其他的序列都要高---因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。)
std::set<ListNode*> node_set;
//将A链表存入set中
while(headA){
node_set.insert(headA);
//指向下一个节点
headA = headA->next;
}
//遍历B链表
while(headB){
//找到了
//这句判断语句是经典的set集合查找是否存在的语句,如果find没找到就会返回end()
//所以只有找到的情况下,才会为真
if(node_set.find(headB) != node_set.end()){
return headB;
}
headB=headB->next;
}
//跳出循环就是没有找到
return NULL;
}
};
思路二:
采用尾对齐的方式(利用数据特点进行查找)
思路一的方法虽然简单,但是很可惜,没能满足最后一点的要求:
其时间复杂度为O(NlogN)而空间复杂度则是O(N)
思路二为较优思路
看图:
image.png
大致意思就是:
先将尾对齐,然后两个链表从相对同样的位置开始遍历,当对应的元素相等时
就是找到交点的时候
ps:开始的有些不理解,一直想不通为什么它可以这样
后来才发现,是因为它数据的特殊性:
从交点开始,之后的所有节点都是共同节点
(这样才叫共享,不会再分开了),所以才可以这样才做
下面是代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//函数:遍历链表,计算链表长度
int get_list_length(ListNode *head){
//长度
int a = 0;
while(head){
a++;
head = head->next;
}
return a;
}
//函数:将指针向前移动至多出节点个数后面的位置,A为长,B为短
ListNode *get_new_list(ListNode *head, int lengthA, int lengthB){
//得到长度之差
int delta = lengthA - lengthB;
//遍历
while(head&&delta){
head = head->next;
delta--;
}
return head;
}
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//求两个链表长度
int lengthA = get_list_length(headA);
int lengthB = get_list_length(headB);
//比较两个链表长度
if(lengthA >= lengthB){
headA = get_new_list(headA, lengthA, lengthB);
}else{
headB = get_new_list(headB, lengthB, lengthA);
}
//各自遍历
while(headA&&headB){
if(headA == headB){
return headA;
}
headA = headA->next;
headB = headB->next;
}
return NULL;
}
};
网友评论