数据结构之链表面试题

3720阅读　0评论2016-05-05　linux_player_c
分类：C/C++

1.前言

关于链表的考察和应用始终是公司考察的重点，因为链表可以衍生出更多具有特性的数据结构（链式栈、队列），那么我们在编写链表这类数据结构的时候一 定要设计好合理的结构体信息，结构体的设计越丰富合理，越有利于程序的编写。今天我们将采用带有控制信息的链表为例，为大家讲解各大公司面试题对链表的考 察。

面试题主要涉及一下部分：

1.链表初始化
2.链表的销毁
3.头部插入
4.尾部插入
5.头部删除
6.尾部删除
7.显示链表信息
8.升序排列链表
9.降序排列链表
10.得到链表的长度
11.合并两个已经排序的链表
12.合并两个已经排序的链表（递归方式）
13.得到链表中间节点的位置
14.得到链表的倒数第k个节点
15.反转链表
16.链表的拷贝
17.逆序打印链表
18.判断两个链表是否有交点
19.找到两个链表的第一个交点
20.在O(1)时间复杂度删除链表节点
21.判断链表是否有环
22.判断链表是否有环
23.找到链表环的入口(简便)
24.找到链表环的入口

链表面试题实现


关于上述所有的问题我们首先引入list.h文件，这个头文件中我们列举出了带有控制信息的链表节点的设计，分为控制信息和节点信息两部分，两者的定义如下所示：


点击(此处)折叠或打开

  1. #define ZERO (0)
  2. #define ONLY_ONE (1)
  3. #define TWO (2)
  4. #define FALSE (0)
  5. #define TRUE (1)

  7. //带有控制信息的单链表
  8. typedef unsigned char Boolean;

  10. //链表节点信息
  11. typedef struct List_node
  12. {
  13.     int data; //数据区域
  14.     struct List_node *next; //链域
  15. }List_node;

  17. //链表控制信息
  18. typedef struct List
  19. {
  20.     struct List_node *head; //链表头部节点
  21.     struct List_node *tail; //链表尾部节点
  22.     int count; //链表节点个数
  23. }List
控制信息可以清楚的知道链表当前的状态，对于链表头和尾部的查找或者说取得链表中的元素个数都可以在O（1）时间复杂度完成。在介绍完基本情况后接下来处理链表的接口问题：


点击(此处)折叠或打开

  1. //链表操作接口
  2. List *init_list(void) ; //链表初始化
  3. void destroy_list(List **list) ; //链表的销毁
  4. Boolean push_front(List *list, int value) ; //头部插入
  5. Boolean push_back(List *list, int value) ; //尾部插入
  6. Boolean pop_front(List *list) ; //头部删除
  7. Boolean pop_back(List *list) ; //尾部删除
  8. void show_list(List *list) ; //显示链表信息
  9. void sort_list_ascend(List *list) ; //升序排列链表
  10. void sort_list_descend(List *list) ; //降序排列链表
  11. int get_list_count(List *list) ; //得到链表的长度

  13. ///
  14. List *merge_two_lists(List *list1, List *list2) ; //合并两个已经排序的链表
  15. List *merge_two_lists_recure(List *list1, List *list2); //同上（递归方式）
  16. List_node *find_mid_node(List *list) ; //得到链表中间节点的位置
  17. List_node *find_revise_node(List *list, int conut) ; //得到链表的倒数第k个节点
  18. List *reverse_list(List *list) ; //反转链表
  19. List *list_dup(List *list) ; //链表的拷贝
  20. void reverse_print_list(List *list) ; //逆序打印链表
  21. Boolean is_list_intersect(List *list1, List *list2) ; //判断两个链表是否有交点
  22. List_node *get_first_common_node(List *list1, List *list2) ; //找到两个链表的第一个交点
  23. void delete_one_node(List *list, List_node *node) ; //在O(1)时间复杂度删除链表节点
  24. Boolean has_circle1(List *list) ; //判断链表是否有环
  25. Boolean has_circle2(List *list, List_node **intersect) ; //判断链表是否有环
  26. List_node *find_circle_first_node1(List *list) ; //找到链表环的入口(简便)
  27. List_node *find_circle_first_node2(List *list) ; //找到链表环的入口

1.链表初始化


点击(此处)折叠或打开

  1. List *init_list(void) //链表初始化
  2. {
  3.     List *list = NULL;

  5.     //链表控制信息申请
  6.     list = (List *)Malloc(sizeof(List));
  7.     bzero(list, sizeof(List));

  9.     return list;
  10. }
        我们这里在动态内存分配中采用了Malloc函数，它是malloc函数的包裹函数，关于包裹函数本人在《unix网络编程》一书中第一次接触，因为库函 数的相关操作会有失败的可能，如果对每次的操作都要进行直接的判断将会使我们的有效代码被淹没在各种判断中，所以建议大家把判断的过程采用包裹函数封装起 来,关于函数调用产生的错误或者一异常问题都在包裹函数中单独处理，这样会使代码更加的简洁。
下面列出malloc包裹函数的具体实现：

点击(此处)折叠或打开

  1. static void *Malloc(size_t size)
  2. {
  3.     void *result = NULL;

  5.     result = malloc(size);
  6.     if(result == NULL){
  7.         fprintf(stderr, "the memory is full!\n");
  8.         exit(1);
  9.     }
  10.     return result;
  11. }
就想上述使用的那样，以后进行动态内存分配只需要调用Malloc即可。


2.链表的销毁

在处理完链表创建，紧接着需要处理的应该是链表的销毁。作为数据结构的处理一定要“善始善终”，这样才不会造成内存的泄露。
链表的销毁我们传入的是链表控制信息的指针的指针，关于细节的问题我们如下图所示：


点击(此处)折叠或打开

  1. void destroy_list(List **list) //链表的销毁
  2. {
  3.     if(list == NULL || *list == NULL){
  4.         return ;
  5.     }
  6.     //1.释放链表本身节点
  7.     while((*list)->count){
  8.         pop_front(*list);
  9.     }
  10.     //2.释放链表的控制信息
  11.     free(*list);
  12.     *list = NULL;
  13. }
这里对于链表的释放在最后一个步骤对链表控制信息类型的指针进行了修改，因为虽然该指针还指向这个控制信息的地址，但是其控制信息已经被释放了，也就是说该指针指向了一个已经非法的地址，所以我们需要将该指针指向NULL。该地址是安全的。


关于push_front（头部插入）、push_back（尾部插入）、pop_front（头部删除）、pop_back（尾部删除）四个接口 是作为一种底层容器的操作而存在的，这样对于线性容器来说，头和尾的四种增加和删除的操作都已经完备了，这在我们对于链表的封装，使其成为栈或者队列有着 重要的意义。

四种接口的实现如下所示：

3.头部插入

图3：头部插入
这里写图片描述

点击(此处)折叠或打开

  1. Boolean push_front(List *list, int value) //头部插入
  2. {
  3.     List_node *node = NULL;

  5.     if(list == NULL){
  6.         return FALSE;
  7.     }
  8.     node = buy_node();
  9.     node->data = value;

  11.     if(list->count == ZERO){ //链表没有元素
  12.         list->head = list->tail = node;
  13.     }else{
  14.         node->next = list->head;
  15.         list->head = node;
  16.     }
  17.     list->count++;
  18.     return TRUE;
  19. }

4.尾部插入

图4：尾部插入

这里写图片描述



点击(此处)折叠或打开

  1. Boolean push_back(List *list, int value) //尾部插入
  2. {
  3.     List_node *node = NULL;

  5.     if(list == NULL){
  6.         return FALSE;
  7.     }
  8.     node = buy_node();
  9.     node->data = value;

  11.     if(list->count == ZERO){ //链表没有元素
  12.         list->head = list->tail = node;
  13.     }else{
  14.         list->tail->next = node;
  15.         list->tail = node;
  16.     }
  17.     list->count++;
  18.     return TRUE;
  19. }

5.头部删除


点击(此处)折叠或打开

  1. Boolean pop_front(List *list) //头部删除
  2. {
  3.     List_node *p_node = NULL;

  5.     if(list == NULL || list->count == ZERO){ //链表不存在或者没有元素，直接退出
  6.         return FALSE;
  7.     }

  9.     p_node = list->head;
  10.     if(list->count == ONLY_ONE){ //如果链表只有一个节点
  11.         list->head = list->tail = NULL;
  12.     }else{
  13.         list->head = list->head->next;
  14.     }
  15.     free(p_node);
  16.     list->count--;
  17.     return TRUE;
  18. }


6.尾部删除

点击(此处)折叠或打开

  1. Boolean pop_back(List *list) //尾部删除
  2. {
  3.     List_node *p_node = NULL;

  5.     if(list == NULL || list->count == ZERO){
  6.         return FALSE;
  7.     }

  9.     p_node = list->head;
  10.     if(list->count == ONLY_ONE){ //只有一个元素
  11.         list->head = list->tail = NULL;
  12.         free(p_node);
  13.     }else{
  14.         while(p_node->next != list->tail){
  15.             p_node = p_node->next;
  16.         }
  17.         free(list->tail);
  18.         list->tail = p_node;
  19.         p_node->next = NULL;
  20.     }
  21.     list->count--;
  22.     return TRUE;
  23. }


7.显示链表信息

7.显示链表的信息是对链表遍历的过程，让一个链表节点指针从链表的头部信息遍历到链表的末尾，对每个节点中的数据区域进行输出则可以显示其节点信息。代码如下所示：


点击(此处)折叠或打开

  1. void show_list(List *list) //显示链表信息
  2. {
  3.     List_node *p_node = NULL;

  5.     if(list == NULL || list->count == ZERO){
  6.         return ;
  7.     }

  9.     //从头到尾对链表节点对数据信息进行输出
  10.     for(p_node = list->head; p_node; p_node = p_node->next){
  11.         printf("%d ", p_node->data);
  12.     }
  13.     printf("\n");
  14. }


8.升序排列链表

对链表的排序我们采用的方式和对数组的排序类似（插入排序），首先我们写出关于数组的排序，然后可以在此基础上模拟出对于链表的排序：

点击(此处)折叠或打开

  1. //对于数组的排序(默认为升序排列)
  2. int i = 0;
  3. int j = 0;

  5. for(i = 0; i < length - 1; ++i){
  6.     for(j = i + 1; j < length; ++j){
  7.         if(array[i] > array[j]){
  8.             swap(&array[i], &array[j], sizeof(array[i]));
  9.         }
  10.     }
  11. }
如果我们把上述的算法转换为链表表现形式：

点击(此处)折叠或打开

  1. #define data_size(p_node) (sizeof(List_node) - sizeof(List_node *))

  3. //链表的升序排列
  4. void sort_list_ascend(List_head head) //链表的升序排序
  5. {
  6.     List_node *p_node = NULL;
  7.     List_node *q_node = NULL;

  9.     //如果链表为空，没有元素或者只有一个元素，不进行排序操作
  10.     if(head == NULL || head->next == NULL
  11.     || head->next->next == NULL){
  12.         return ;
  13.     }

  15.     for(p_node = head->next; p_node != NULL; p_node = p_node->next){
  16.         for(q_node = p_node->next; q_node != NULL; q_node = q_node->next){
  17.             if(p_node->data > q_node->data){
  18.                 //只交换数据域
  19.                 swap(p_node, q_node, data_size(p_node));
  20.             }
  21.         }
  22.     }
  23. }

9.降序排列链表

降序的处理方式和升序相同，代码如下所示：


点击(此处)折叠或打开

  1. void sort_list_descend(List_head head) //链表的升序排序
  2. {
  3.     List_node *p_node = NULL;
  4.     List_node *q_node = NULL;

  6.     //如果链表为空，没有元素或者只有一个元素，不进行排序操作
  7.     if(head == NULL || head->next == NULL
  8.     || head->next->next == NULL){
  9.         return ;
  10.     }

  12.     for(p_node = head->next; p_node != NULL; p_node = p_node->next){
  13.         for(q_node = p_node->next; q_node != NULL; q_node = q_node->next){
  14.             if(p_node->data < q_node->data){
  15.                 //只交换数据域
  16.                 swap(p_node, q_node, data_size(p_node));
  17.             }
  18.         }
  19.     }
  20. }
关于上述的两个排序算法其实只有一个符号的区别，良好的设计应该是减少代码的重复率，也就是我们应该给函数传递第二个参数来表示采用何种排序方式（升序或者降序）。


10.得到链表的长度

关于链表的长度问题，采用以前的方式我们需要将链表从头到尾进行遍历，如果链表的长度过于长的话，这样O（n）的时间复杂度是我们无法能够承受的。可是如今的链表可以通过控制信息中的count成员再O（1）的时间复杂度得到。

点击(此处)折叠或打开

  1. int get_list_count(List *list) //得到链表的长度
  2. {
  3.     if(list == NULL){
  4.         return -1;
  5.     }
  6.     return list->count;
  7. }


11.合并两个已经排序的链表

要对两个已经排序的链表进行合并（以升序为例），其主要思想如下：
两个链表A、B的第一个节点信息都是当前链表中值最小的一个，我们定义出两个链表节点指针p、q分别指向链表的第一个节点，然后对两个指针所指向的节点内 容进行”大小的比较“，如果p所指向的节点的值小于q所指向的节点的值。那么我们就以p所指向的节点的值构造出结果链表的当前节点，然后让p向后移动，反 之q亦然。如果p和q其中某个指针提前遍历到末尾，则把对方的剩余部分尾部追加到结果链表中。代码如下所示：


点击(此处)折叠或打开

  1. List *merge_two_lists(List *list1, List *list2) //合并两个已经排序的链表
  2. {
  3.     List *list3 = NULL;
  4.     List_node *list1_move = NULL;
  5.     List_node *list2_move = NULL;

  7.     if(list1 == NULL || list2 == NULL){
  8.         return list3;
  9.     }

  11.     list3 = init_list();

  13.     list1_move = list1->head;
  14.     list2_move = list2->head;

  16.     //进行两个链表的比较，把较小的元素尾插到list3中
  17.     while(list1_move != NULL && list2_move != NULL){
  18.         if(list1_move->data < list2_move->data){
  19.             //如果list1_move指向的值小于list2_move，则尾插list1_move的值
  20.             push_back(list3, list1_move->data);
  21.             list1_move = list1_move->next;
  22.         }else{
  23.             push_back(list3, list2_move->data);
  24.             list2_move = list2_move->next;
  25.         }
  26.     }

  28.     //当两个链表中有任意一个遍历完成，则把另外一个链表整体尾插到list3
  29.     while(list2_move != NULL){
  30.         push_back(list3, list2_move->data);
  31.         list2_move = list2_move->next;
  32.     }

  34.     while(list1_move != NULL){
  35.         push_back(list3, list1_move->data);
  36.         list1_move = list1_move->next;
  37.     }

  39.     return list3;
  40. }
上述采用的是迭代的策略处理，如果纯粹为了锻炼编程技巧，我们也可以采用递归的策略对两个已经排序的链表进行合并，在思想上是大同小异的。但是代码的书写上有很大的差别。


12.合并两个已经排序的链表（递归方式）


点击(此处)折叠或打开

  1. static List_node *copy_list(List_node *src_list) //通过链表节点拷贝
  2. {
  3.     List_node *result = NULL;
  4.     List_node *p_node = NULL;
  5.     List_node *q_node = NULL;

  7.     if(src_list == NULL){
  8.         return result;
  9.     }

  11.     //如果原链表存在进行拷贝
  12.     result = buy_node();
  13.     p_node = q_node = result;
  14.     result->data = src_list->data;
  15.     src_list = src_list->next;

  17.     while(src_list != NULL){
  18.         //如钩src指向不为空，生成一个节点并赋值，然后判断src的next
  19.         p_node = buy_node();
  20.         p_node->data = src_list->data;
  21.         q_node->next = p_node;
  22.         q_node = p_node;
  23.         src_list = src_list->next;
  24.     }

  26.     return result;
  27. }


  30. static List_node *merge_lists(List_node *list1_first,
  31.                               List_node *list2_first){
  32.     List_node *result = NULL;

  34.     if(list1_first == NULL){
  35.         //如果list1链表归并结束，把list2剩余部分添加到结果链表的末尾
  36.         return copy_list(list2_first);
  37.     }else if(list2_first == NULL){
  38.         return copy_list(list1_first);
  39.     }

  41.     if(list1_first->data < list2_first->data){
  42.         result = buy_node();
  43.         result->data = list1_first->data;
  44.         result->next = merge_lists(list1_first->next, list2_first);
  45.     }else{
  46.         result = buy_node();
  47.         result->data = list2_first->data;
  48.         result->next = merge_lists(list1_first, list2_first->next);
  49.     }
  50.     return result;
  51. }

  53. List *merge_two_lists_recure(List *list1, List *list2) //合并两个已经排序的链表（递归方式）
  54. {
  55.     List *list3 = NULL;

  57.     if(list1 == NULL && list2 == NULL){
  58.         return list3;
  59.     }

  61.     if(list1 == NULL){
  62.         return list3 = list_dup(list2);
  63.     }else if(list2 == NULL){
  64.         return list3 = list_dup(list1);
  65.     }

  67.     //对结果链表进行初始化
  68.     list3 = init_list();

  70.     list3->head = merge_lists(list1->head, list2->head);
  71.     list3->count = list1->count + list2->count;
  72.     list3->tail = find_revise_node(list3, 1); //找到倒数第一个节点赋值给tail
  73.    // printf("count:%d\n", list3->count);
  74.     return list3;
  75. }

在上述的程序中我们不仅要处理好链表节点的合并，还要对链表的控制信息进行更新，关于控制信息中链表的末尾节点。我们只能采取比较笨的方法，使用函数 find_revise_node找到链表末尾节点的地址，把它赋值给控制信息的tail元素。关于如何寻找链表的倒数第n个节点，我们在下一个接口进行 了实现。


13.得到链表的倒数第k个节点

寻找倒数第k个节点的方法，如果没有链表控制信息，我们只能采用较为传统的方式：
给定两个链表节点指针p和q，让他们指向链表的第一个节点位置，让其中一个指针p首先移动k个节点，然后让另外一个指针q和p在不同的起始位置一起向后移动，当p指针到到末尾的时候，此时q指针指向链表的倒数第k个节点（代码自己实现）。
在我们已经具有链表控制信息的时候，可以得知链表的总数为count,如果我们想要找到链表的倒数第k个节点的话，所需要移动的步长move_count与其之间的关系如下所示： 

move_count = count - k;   (总数 - 倒数第k个)


	
	

		
		

			点击(此处)折叠或打开
		


	


	

		
		
    
			
			
  1. 
				List_node *find_revise_node(List *list, int count) //得到链表的倒数第k个节点 
			
    2. 

			
  2. 
				{
			
    3. 

			
  3. 
				    List_node *result = NULL; 
			
    4. 

			
  4. 
				    int move_count = 0; 
			
    5. 

			
  5. 
				
			
    6. 

			
  6. 
				    if(list == NULL || list->count == ZERO
			
    7. 

			
  7. 
				    || count <= ZERO || count > list->count){ 
			
    8. 

			
  8. 
				        return result; 
			
    9. 

			
  9. 
				    }
			
    10. 

			
  10. 
				
			
    11. 

			
  11. 
				    // 9 1 (9 - 1) (list->count - count) 
			
    12. 

			
  12. 
				    move_count = list->count - count; 
			
    13. 

			
  13. 
				    result = list->head; 
			
    14. 

			
  14. 
				    while(move_count--){ 
			
    15. 

			
  15. 
				        result = result->next; 
			
    16. 

			
  16. 
				    }
			
    17. 

			
  17. 
				    return result; 
			
    18. 

			
  18. 
				}
			
    19.

14.得到链表中间节点的位置

得到链表中间位置的方式和得到链表倒数第k个节点的方式非常的类似，依然给它两个指向链表第一个节点的指针p和q,此时采用快慢结合的方式，让p指 针每次移动一个节点，让q指针每次移动两个节点，二者依次进行上述的步骤，当q指针移动到链表的末尾时，p指针所指向的位置为链表的中点。

我们拥有链表的控制信息，那么在查找的时候更加方便，到达中间节点所需要移动的步长是count / 2 (也可以用位运算count >> 1)。

代码如下图所示:


点击(此处)折叠或打开

  1. List_node *find_mid_node(List *list) //得到链表中间节点的位置
  2. {
  3.     List_node *mid = NULL;
  4.     int move_count = 0;

  6.     if(list == NULL || list->count == ZERO){
  7.         return mid;
  8.     }

  10.     mid = list->head;

  12.     //找到链表中间节点
  13.     move_count = list->count >> 1; // 9 1001 --> 0100 4
  14.                                      // 12 1100 --> 0110 6
  15.     while(move_count--){
  16.         mid = mid->next;
  17.     }
  18.     return mid;
  19. }

15.反转链表
链表的反转我们需要借助多个指针配合操作，并且关于反转的操作分为以下几个情况：

1.如果链表只有一个节点，则不需要进行反转。
2.如果链表拥有两个节点，那么反转的操作相对简单。
3.如果链表拥有三个或三个以上的节点，则需要使用迭代的方式对链表进行反转。


点击(此处)折叠或打开

  1. List *reverse_list(List *list) //反转链表
  2. {
  3.     List_node *p = NULL;
  4.     List_node *q = NULL;
  5.     List_node *m = NULL;


  8.     //如果链表没有节点或者只有一个节点
  9.     if(list == NULL || list->count <= ONLY_ONE){
  10.         return list;
  11.     }

  13.     //两个节点
  14.     if(list->count == TWO){
  15.         list->tail->next = list->head;
  16.         list->head->next = NULL;
  17.     }else{
  18.         //三个或三个以上
  19.         p = list->head;
  20.         q = p->next;
  21.         m = q->next;

  23.         p->next = NULL;
  24.         do{
  25.             q->next = p;
  26.             p = q;
  27.             q = m;
  28.             m = m->next;
  29.         }while(m != NULL);
  30.         q->next = p;
  31.     }
  32.     swap(&(list->head), &(list->tail), sizeof(List_node *));
  33.     return list;
  34. }

可以看到倒数第二行有一个swap(&(list->head), &(list->tail), sizeof(List_node *));的操作。该函数可以交换任意类型的两个变量（被交换的双方必须是类型相同的），也就是实现了通用编程的思想。

swap函数的实现原型如下所示：


点击(此处)折叠或打开

  1. static void swap(void *a, void *b, int length)
  2. {
  3.     void *temp = Malloc(length);
  4.     //使用内存拷贝的方式交换a、b两个指针所指向的空间
  5.     memcpy(temp, a, length);
  6.     memcpy(a, b, length);
  7.     memcpy(b, temp, length);
  8.     free(temp);
  9. }

16.链表的拷贝

对于链表的拷贝我们并没有只是让一个指针指向已经存在的链表，虽然这样也可以达到对该链表的操作，一旦该链表不存在，其中的一个或多个指针将会指向一个不可存在的地址。所以我们需要实现深拷贝，也就是说要有真实存在的另一个链表，而不是只拥有简单的地址。


点击(此处)折叠或打开

  1. static List_node *copy_list(List_node *src_list) //通过链表节点拷贝
  2. {
  3.     List_node *result = NULL;
  4.     List_node *p_node = NULL;
  5.     List_node *q_node = NULL;

  7.     if(src_list == NULL){
  8.         return result;
  9.     }

  11.     //如果原链表存在进行拷贝
  12.     result = buy_node();
  13.     p_node = q_node = result;
  14.     result->data = src_list->data;
  15.     src_list = src_list->next;

  17.     while(src_list != NULL){
  18.         //如钩src指向不为空，生成一个节点并赋值，然后判断src的next
  19.         p_node = buy_node();
  20.         p_node->data = src_list->data;
  21.         q_node->next = p_node;
  22.         q_node = p_node;
  23.         src_list = src_list->next;
  24.     }

  26.     return result;
  27. }

17.逆序打印链表

看到这个问题，很多同学的第一个反映就是刚才我们已经实现了链表的翻转，将翻转的链表进行输出就仿佛是对链表进行了逆序的打印。但这违反了一个基本 的原则，就是未经允许不可对原数据结构进行修改。所以我们要转换思路，需要采用递归的策略，如果理解了函数的栈帧，那最后一次调用的函数（链表的末尾）执 行打印操作的时候就是在输出最后一个节点的数据信息，紧接着函数的栈帧进行销毁，重复上述的操作，即可把链表的数据信息进行逆序的输出。



点击(此处)折叠或打开

  1. static void re_print_list(List_node *node)
  2. {
  3.     // 12 20 25 30 NULL
  4.     //
  5.     if(node == NULL){
  6.         return ;
  7.     }else{
  8.         re_print_list(node->next);
  9.         printf("%d ", node->data);
  10.     }
  11. }

  13. void reverse_print_list(List *list) //逆序打印链表
  14. {
  15.      if(list == NULL || list->count == ZERO){
  16.          return ;
  17.      }

  19.      re_print_list(list->head);
  20.      printf("\n");
  21. }


18.判断两个链表是否有交点

判断两个链表是否具有交点，我们需要知晓一旦两个链表A、B具有交点的话，那么A、B链表的最后一个节点一定相交。基于上述的理论我们得到如下的代码：



点击(此处)折叠或打开

  1. Boolean is_list_intersect(List *list1, List *list2) //判断两个链表是否有交点
  2. {
  3.     if(list1 == NULL || list2 == NULL
  4.     || list1->count == ZERO || list2->count == ZERO){
  5.         return FALSE;
  6.     }
  7.     return list1->tail == list2->tail;
  8. }

19.找到两个链表的第一个交点

一旦我们确定了两个链表具有交点，在这样一个条件下想要求出第一个交点也是比较轻松的事情。基本的思想如下图所示:

图 链表第一个交点
这里写图片描述

代码如下所示：



点击(此处)折叠或打开

  1. List_node *get_first_common_node(List *list1, List *list2) //找到两个链表的第一个交点
  2. {
  3.     //1.先计算两个链表的长度，求出差值dis，让较长链表先移动dis距离；
  4.     //2.两个链表从相同长度开始依次向后移动，每移动一次比较两个指针是
  5.     //否相等，如果相等则该地址为两个链表的第一个交点。
  6.     int list1_len = 0;
  7.     int list2_len = 0;
  8.     int dis = 0;
  9.     List_node *p_node = NULL;
  10.     List_node *q_node = NULL;

  12.     //1.
  13.     if(list1 == NULL || list2 == NULL
  14.     || list1->count == ZERO || list2->count == ZERO
  15.     || is_list_intersect(list1, list2) == FALSE){
  16.         return NULL;
  17.     }
  18.     list1_len = list1->count;
  19.     list2_len = list2->count;

  21.     p_node = list1->head;
  22.     q_node = list2->head;

  24.     if(list1_len > list2_len){ //链表1比链表2长
  25.         dis = list1_len - list2_len;
  26.         while(dis--){
  27.             p_node = p_node->next;
  28.         }
  29.     }else{
  30.         dis = list2_len - list1_len;
  31.         while(dis--){
  32.             q_node = q_node->next;
  33.         }
  34.     }

  36.     //2.
  37.     while(p_node != q_node){
  38.         p_node = p_node->next;
  39.         q_node = q_node->next;
  40.     }

  42.     return p_node;
  43. }


20.在O(1)时间复杂度删除链表节点

删除一个链表节点按照之前的说法必须要从头到尾进行遍历，找到被删除节点的前一个节点，然后让前一个节点的指向越过被删除节点，指向被删除节点的后一个节点。
可是现在题目的要求需要我们想到更加巧妙的方式，具体的过程如下图所示：

图 删除节点
这里写图片描述

可是这样的问题是常规现象，如果要删除的节点是最后一个节点，那么最后一个节点的next指向为不可访问的地址。那么对其操作将会引发段错误，此时需要调用链表操作删除尾部节点（pop_back）。



点击(此处)折叠或打开

  1. void delete_one_node(List *list, List_node *node) //在O(1)时间复杂度删除链表节点
  2. {
  3.     List_node *p_node = NULL;

  5.     if(list == NULL || node == NULL){
  6.         return ;
  7.     }

  9.     if(node->next != NULL){ //该结点不在末尾
  10.         p_node = node->next;
  11.         node->data = p_node->data;
  12.         node->next = p_node->next;
  13.         free(p_node);
  14.     }else{
  15.         pop_back(list);
  16.     }
  17. }

21.判断链表是否有环

首先我们列举出链表右环的几种情况：
这里写图片描述

如果要判断一个链表是否有环，我们采用以下策略：
1.如果链表有环，末尾指针的指向一定是指向链表其中的一个节点形成闭路，这是一个环状结构。那么我们可以定义两个指针，一个快，一个慢。快指针每次移动 两个步长，慢指针每次移动一个步长。这样的话如果链表没有环状结构，一定是快指针率先走到链表的末尾，如果链表拥有环状结构，那么快慢指针最终会在链表的 环中进行追击运动，然后两者会在环中的某一个节点相遇。代码如下所示：



点击(此处)折叠或打开

  1. Boolean has_circle(List *list, List_node **instersect)
  2. {
  3.     List_node *slow = NULL;
  4.     List_node *fast = NULL;

  6.     if(list == NULL || list->count < TWO){
  7.          return FALSE;
  8.     }

  10.     slow = list->head;
  11.     fast = list->head;

  13.     //1.fast每次向后移动两个节点,slow每次移动一个节点
  14.     //
  15.     while(fast != NULL && fast->next != NULL){
  16.         fast = fast->next->next;
  17.         slow = slow->next;

  19.         if(fast == slow){ //链表有环，并且该点在环内
  20.             *intersect = fast;
  21.             return TRUE;
  22.         }
  23.     }
  24.     return FALSE；
  25. }


24.找到链表环的入口

在判断了链表是否有环后，我们需要取判断链表环的入口节点，这个直接进行判断是非常困难的，我们需要把问题进行转换。
转换的方式如下图所示：

链表环转换为相交问题
这里写图片描述


点击(此处)折叠或打开

  1. List_node *find_circle_first_node2(List *list) //找到带环链表的环入口节点
  2. {
  3.     List_node *intersect = NULL;
  4.     List_node *list2_head = NULL;
  5.     List_node *list1_head = NULL;
  6.     List_node *p_node = NULL;
  7.     List_node *q_node = NULL;
  8.     int list1_len = 1;
  9.     int list2_len = 1;
  10.     int dis = 0 ;

  12.     if(list == NULL || list->count < TWO
  13.     || has_circle(list, &intersect) == FALSE){
  14.         return NULL;
  15.     }

  17.     //相交点的下一个点为list2的头结点，把求环入口点
  18.     //问题转化为求两个相交链表的第一个交点
  19.     p_node = list1_head = list->head;
  20.     q_node = list2_head = intersect->next;


  23.     //计算两个链表的长度
  24.     while(p_node != intersect){
  25.         list1_len++;
  26.         p_node = p_node->next;
  27.     }

  29.     while(q_node != intersect){
  30.         list2_len++;
  31.         q_node = q_node->next;
  32.     }

  34.    p_node = list1_head;
  35.    q_node = list2_head;

  37.     //让较长的链表先移动长度差值的步数
  38.    if(list1_len > list2_len){
  39.        dis = list1_len - list2_len;
  40.        while(dis--){
  41.            p_node = p_node->next;
  42.        }
  43.    }else{
  44.        dis = list2_len - list1_len;
  45.        while(dis--){
  46.            q_node = q_node->next;
  47.        }
  48.    }

  50.    while(p_node != q_node){
  51.        p_node = p_node->next;
  52.        q_node = q_node->next;
  53.    }
  54.    return p_node;
  55. }


接下来我们编写测试代码：

点击(此处)折叠或打开

  1. //main.c
  2. int main(int argc, char **argv)
  3. {
  4.     List *list1 = NULL;
  5.     List *list2 = NULL;
  6.     List *list3 = NULL;
  7.     List_node *mid = NULL;

  9.     int i = 0;

  11.     list1 = init_list(); //链表的初始化（创建控制信息）

  13.     for(i = 0; i < 10; ++i){
  14.         push_front(list1, rand() % 100);
  15.     }

  17.     list2 = init_list(); //链表的初始化（创建控制信息）

  19.     for(i = 0; i < 10; ++i){
  20.         push_front(list2, rand() % 100);
  21.     }

  23.     printf("before sort:\n");
  24.     show_list(list1);
  25.     show_list(list2);

  27.     sort_list_ascend(list1);
  28.     sort_list_ascend(list2);

  30.     printf("after sort:\n");
  31.     show_list(list1);
  32.     show_list(list2);

  34.     printf("merge result:\n");
  35.     //list3 = merge_two_lists(list1, list2);
  36.     list3 = merge_two_lists_recure(list1, list2);
  37.     show_list(list3);

  39.     mid = find_mid_node(list1);
  40.     if(mid != NULL){
  41.         printf("list1 mid node value:%d\n", mid->data);
  42.     }

  44.     list3 = reverse_list(list3);
  45.     show_list(list3);

  47.     reverse_print_list(list3);

  49.     destroy_list(&list1); //链表的销毁
  50.     destroy_list(&list2);
  51.     destroy_list(&list3);
  52.     return 0;
  53. }
小结：
上述的22个面试题基本涵盖了链表的常见操作，希望可以给大家的笔试和面试带来帮助，另外欢迎大家能够给出更好的方案，可以共同探讨进步。


上一篇：数据结构之链表
下一篇：没有了