求两个链表的交点

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

数据结构之串

基本概念 串(string)是由零个或多个字符组成的有限序列,又名叫字符串。形如s="a,b,c.."。ai(1 ≤ i ≤ n)可以是字母、数字或其他字符,i...

2788
来自专栏赵俊的Java专栏

链表插入排序

2084
来自专栏程序员与猫

常见算法设计方法-分治法

分治法(Devide & Conquer) 1. 常见步骤 Devide 把一个问题的特殊实例划分成若干个子问题 Conquer 递归地解决每个子问题 Co...

2119
来自专栏coding

Beautiful Soup库详解安装Beautiful Soup 介绍节点选择器方法选择器css 选择器

只需要在初始化 Beautiful Soup 时,将第二个参数设置为 lxml 即可

2413
来自专栏Jack-Cui

67.Add Binary(String-Easy)

Given two binary strings, return their sum (also a binary string). For example, ...

1806
来自专栏维C果糖

编程思想 之「操作符」

在 Java 编程的过程中,我们对数据的处理,都是通过操作符来实现的。例如,用于赋值的赋值操作符、用于运算的运算操作符、用于比较的比较操作符,还包括逻辑操作符、...

4206
来自专栏java系列博客

MD5压缩算法

3286
来自专栏Java爬坑系列

【Java入门提高篇】Day9 Java内部类——静态内部类

  今天来说说Java中的最后一种内部类——静态内部类   所谓的静态内部类,自然就是用static修饰的内部类,那用static修饰过后的内部类,跟一般的内部...

2296
来自专栏hbbliyong

Python正则进阶

  返回一个列表,如果正则表达式中没有分组,则列表中包含的是所有匹配的内容,如果正则表达式中有分组,则列表中的每个元素是一个元组,元组中包含子分组中匹配到的内容...

1353
来自专栏Android群英传

Swift vs. Kotlin 漫谈系列之类与继承

2064

扫码关注云+社区

领取腾讯云代金券