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

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