剑指offer之求两个链表的第一个公共节点

举报
chenyu 发表于 2021/07/27 01:01:04 2021/07/27
1.3k+ 0 0
【摘要】 1 问题 输入两个链表,找出它们的第一个公共结点。 含有公共节点的两个链表的结构类似于下图中的链表: 1 -> 2 -> 3 -> 4 ->5                2 -> 4 ->5 可以看到两个链表中有一个公共节点,其中4节点就是这两个链...

1 问题

输入两个链表,找出它们的第一个公共结点。

含有公共节点的两个链表的结构类似于下图中的链表:

1 -> 2 -> 3 -> 4 ->5

               2 -> 4 ->5

可以看到两个链表中有一个公共节点,其中4节点就是这两个链表的公共节点  

 

2 分析

既然题目是求公共节点,说明一定存在这个节点,然后我们可以发现两个链表的尾巴是一样,都重合了是Y性结构,我们先把长的链表的头移动到短的头那里,然后一个接着下一个比较就行

3 代码实现


      #include <stdio.h>
      #include <stdlib.h>
      typedef struct Node
      {
       int value;
       struct Node *next;
      } Node;
      /*
       * 初始化结构体
       */
      struct Node* init(struct Node *node, int value)
      {
       node = (struct Node*)malloc(sizeof(Node));
      if (node != NULL)
       {
       node->value = value;
      //这个地方不要忘记设置为NULL
       node->next = NULL;
      return node;
       }
      return NULL;
      }
      /*
       * 获取链表的长度
       */
      int length(Node *head)
      {
      if (head == NULL)
      return 0;
       Node *p = head;
      int length = 0;
      while (p != NULL)
       {
       length++;
       p = p->next;
       }
      return length;
      }
      /**
       * 找到第一个公共的节点
       */
      struct Node* get_common(Node *head1, Node *head2)
      {
      if (head1 == NULL || head2 == NULL)
       {
      return NULL;
       }
      int list1_length = length(head1);
      int list2_length = length(head2);
       Node *short_head = NULL;
       Node *long_head = NULL;
      int sub_len = 0;
      if (list1_length > list2_length)
       {
       short_head = head2;
       long_head = head1;
       sub_len = list1_length - list2_length;
       }
      else
       {
       short_head = head1;
       long_head = head2;
       sub_len = list2_length - list1_length;
       }
      //移动长链表,确保两个链表一样长
      while (sub_len > 0)
       {
       sub_len--;
       long_head = long_head->next;
       }
      while (short_head != NULL && long_head != NULL)
       {
      if (short_head->value == long_head->value)
       {
      return short_head;
       }
       short_head = short_head->next;
       long_head = long_head->next;
       }
      return NULL;
      }
      int main()
      {
       Node *n1 = NULL;
       Node *n2 = NULL;
       Node *n3 = NULL;
       Node *n4 = NULL;
       Node *n5 = NULL;
       Node *m1 = NULL;
       Node *m2 = NULL;
       Node *m3 = NULL;
       n1 = init(n1, 1);
       n2 = init(n2, 2);
       n3 = init(n3, 3);
       n4 = init(n4, 4);
       n5 = init(n5, 5);
       m1 = init(m1, 2);
       m2 = init(m2, 4);
       m3 = init(m3, 5);
      if (n1 && n2 && n3 && n4 && n5)
       {
       n1->next = n2;
       n2->next = n3;
       n3->next = n4;
       n4->next = n5;
       }
      if (m1 && m2 && m3)
       {
       m1->next = m2;
       m2->next = m3;
       }
       Node *node = get_common(n1, m2);
      if (node)
       {
      printf("common node value is: %d\n", node->value);
       }
      else
       {
      printf("two list do not common value\n");
       }
      if (n1) {free(n1); n1 = NULL;}
      if (n2) {free(n2); n2 = NULL;}
      if (n3) {free(n3); n3 = NULL;}
      if (n4) {free(n4); n4 = NULL;}
      if (n5) {free(n5); n5 = NULL;}
      if (m1) {free(m1); m1 = NULL;}
      if (m2) {free(m2); m1 = NULL;}
      if (m3) {free(m3); m1 = NULL;}
      return 1;
      }
  
 

4 运行结果

common node value is: 4
 

 

 

5 总结

如果我们求链表的长度,一般是这样的函数


      /*
       * 获取链表的长度
       */
      int length(Node *head)
      {
      if (head == NULL)
      return 0;
       Node *p = head;
      int length = 0;
      while (p != NULL)
       {
       length++;
       p = p->next;
       }
      return length;
      }
  
 

一定要记到骨髓里面去。

文章来源: chenyu.blog.csdn.net,作者:chen.yu,版权归原作者所有,如需转载,请联系作者。

原文链接:chenyu.blog.csdn.net/article/details/86501502

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称,即可参与社区互动!

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。