前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >求两个链表的交点

求两个链表的交点

作者头像
小飞侠xp
发布2018-08-29 14:37:04
8940
发布2018-08-29 14:37:04
举报
文章被收录于专栏:书山有路勤为径

已知链表A的头节点指针headA,链表B的头节点指针headB,两个链表相交,求两链表交点对应的节点。 [](LeetCode 160)

数据结构

代码语言:javascript
复制
struct ListNode{
    int val;
    ListNode * next;
    ListNode(int x) : val(x),next(NULL){}
};
这里先简单介绍一下Set的使用

判断两个数组是否有相同元素

代码语言:javascript
复制
#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中的第一个节点地址,即是两个链表的交点。

代码语言:javascript
复制
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.遍历链表,计算链表长度
代码语言:javascript
复制
int get_list_length(ListNode *head){
    int len = 0;
    while(head){
    len++;
    head = head->next;
}
    return len;
}
2.移动指针对齐
代码语言:javascript
复制
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.步骤
代码语言:javascript
复制
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;
}
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.03.06 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 这里先简单介绍一下Set的使用
  • 算法设计
    • 1.方法一:使用set求交集
      • 方法二:
        • 1.遍历链表,计算链表长度
          • 2.移动指针对齐
            • 3.步骤
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档