已知链表A的头节点指针headA,链表B的头节点指针headB，两个链表相交，求两链表交点对应的节点。
[](LeetCode 160)
数据结构
struct ListNode{
int val;
ListNode * next;
ListNode(int x) : val(x),next(NULL){}
};
这里先简单介绍一下Set的使用
判断两个数组是否有相同元素
#include<set>
int main(){
std::set<int> test_set;//STL set
const int A_Len = 7;
const int B_Len = 8;
int a[A_Len] = {5,1,4,8,10,1,3};
int b[B_Len] = {2,7,6,3,1,6,0,1};
}
for (int i =0;i < A_Len;i++){
test_set.insert(a[i]);//将数组a的元素插入set
}
for(int i = 0; i< B_Len;i++){//检查数组b中的元素是否在set中
if(test_set.find(b[i]) != test_set.end()){
printf("b[%d] = %d in array A.\n",i,b[i]);
}
return 0;
}
算法设计
1.方法一：使用set求交集
1.遍历链表A，将A中节点对应的指针(地址)，插入set
2.遍历链表B，将B中节点对应的指针(地址)，在set中查找 ，发现在set中的第一个节点地址，即是两个链表的交点。
class Solution{
public:
ListNode *getIntersectionNode(ListNode *headA,ListNode *headB){
std :: set<ListNode*> node_set;
while(headA){
node_set.insert(headA);
headA = headA->next; //遍历链表A
}
while(headB){
if(node_set.find(headB) != node_set.end()){//当在head B中找到第一个出现在node_set中的节点
return headB;
}
headB = headB->next;
}
return NULL;
}
}
方法二：
- 计算headA链表长度，计算headB链表长度，较长的链表多出的长度
- 将较长链表指针移动到和较短链表指针对齐的位置
- headA与headB同时移动，当两指针指向同一个节点时，即找到了
1.遍历链表，计算链表长度
int get_list_length(ListNode *head){
int len = 0;
while(head){
len++;
head = head->next;
}
return len;
}
2.移动指针对齐
ListNode *forward_long_list(int long_len, int short_len,ListNode *head){
int delta = long_len -short_len;
while(head && delta){
head =head->next;
delta --;
}
return head;
}
3.步骤
class Solution{
public:
ListNode * getIntersectionNode(ListNode *headA,ListNode *headB){
int list_A_len = get_list_length(headA);
int list_B_length = get_list_length(headA);//求A，B两个链表长度
if(list_A_len >list_B_len){
headA = forward_long_list(list_A_len,list_B_len,headA)
}
else{
headB =forward_long_list(list_B_len,list_A_len,headB);// 如果链表B长，移动headB到对应位置
}
while(headA && headB){
if(headA == headB){// 当两指针指向了同一个节点，说明找到了
return headA;
}
headA =headA->next;
headB =headB->next;
}
return NULL;
}
}
