求两个链表的交点

已知链表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;
}
}

复制