三道链表经典面试题-技术圈

链表在工作中是很常用的数据结构也是面试必考的数据结构，对于链表一定要能灵活运用方能快速回答出面试官提的问题，并且经常要求现场手写代码，这里我总结了单链表三道经典面试题并以源码的形式呈现解决方案。

—

翻转单链表

翻转链表基本上是最简单的链表相关面试/笔试题了，核心思想则是：

用一个局部变量存储链表头
从第二个结点开始遍历单链表
将当前遍历的结点采用头插法插入新链表

这里我们将会用到我前面的文章所实现的单链表，还不会写单链表的同学请参考这篇文章，我们先看一下翻转链表的函数声明。

extern list_t *convert_list(list_t *list); //翻转链表

我们需要传入链表头结点，返回值则是翻转后的链表头结点。函数实现代码如下：

list_t *convert_list(list_t *list){
    if(list == NULL){
        return NULL;
    }

    list_t *head = list; //新链表头结点
    list_t *temp = NULL;
    list = list->next;
    head->next = NULL;

    while(list != NULL){
        temp = list; //保存遍历过的结点
        list = list->next; //遍历下一个结点
        temp->next = head; //头查法插入链表
        head = temp; //更新链表头结点
    }

    return head;
}

—

查找单链表倒数第k个结点

查找倒数第k个结点的方法有很多，比如先遍历到链表尾部，如果链表的长度length小于k那么k值是非法的则找不到结点，若k值是合理的，再往前遍历到第k个结点即可。或者求出链表长度length，如果length小于k那么k值是非法的则找不到结点，否则再遍历到第length - k个结点，以上两种方法都要遍历2次，而且也是我们下意识就能想到的，很显然面试官基本不会这么考你，那么有没有一种只需要遍历一遍就能找到单链表倒数第k个结点的方法呢？

现在有一种方法能解决这个问题，核心思想则是：

需要2个指针，指针1先行遍历，直到指针1遍历到第k个结点时，指针2从链表头开始遍历。
指针1遍历到尾部的时候，指针2指向的结点就是倒数第k个结点。

函数声明如下：

extern list_t *get_last_k_node(list_t *list, int k); //获取倒数第K个结点

实现代码如下：

list_t *get_last_k_node(list_t *list, int k){
    if(list == NULL || k <= 0){
        return NULL;
    }

    int index = 0;
    list_t *head = list;

    while(list != NULL){
        index++;
        list = list->next;
        if(index > k){
            //前一个指针已经移动了k个结点，则后一个指针开始移动
            //直到前一个指针已经移动到链表尾部，则后一个指针指向的就是倒数第k个结点
            head = head->next;
        }
    }

    //k值不正确，则找不到目标结点
    if(index < k){
        return NULL;
    }

    return head;
}

—

判断单链表是否有环

我们知道一个链表如果有环，那么只要你不断的遍历总会经过原来遍历过的结点，如果无环，肯定不会经过遍历过的结点。判断单链表是否有环，参考校运会的场景，2个人同时在操场跑步，如果有一个人跑得很快，一个跑得很慢，由于跑道是围绕操场的，是一个环，那么跑得快的最后总会追上跑得慢的。回到计算机编程中我们同样可以采用这样的思路解决问题。

定义2个指针，一个快指针，一个慢指针。
快指针先从链表头开始遍历，快指针移动后，紧接着慢指针移动，快指针每次移动2个结点，慢指针每次移动1个结点。
检查快指针是否等于慢指针（快指针追赶上了慢指针）。有则代表有环，反之如果快指针已经到达链表尾部则无环。

因为我们在上一篇文章中只实现了无环单链表，为了测试需要我们定义一个将无环单链表转成有环单链表函数函数定义如下。

extern list_t *transfer_to_ring_list(list_t *list); //将单链表转成环形链表

实现代码如下：

list_t *transfer_to_ring_list(list_t *list){
    if(list == NULL){
        return NULL;
    }

    list_t *head = list;
    while(list->next != NULL){
        list = list->next;
    }
    list->next = head;

    return head;
}

判断单链表是否有环函数声明如下：

extern bool is_there_a_ring(list_t *list); //判断链表是否有环

实现代码如下：

bool is_there_a_ring(list_t *list){
    if(list == NULL){
        return false;
    }

    list_t *node = list;
    while(list != NULL){
        if(list->next != NULL){
            list = list->next->next; //首指针移动2个结点
            //两个指针相遇说明链表有环
            if(list == node){
                return true;
            }
        }else{
            break;
        }
        if(node != NULL){
            node = node->next; //后面的指针移动一个结点
        }
    }

    return false;
}

—

结果验证

最后我们写一个小程序验证三道单链表经典面试题代码是否正确，代码如下：

#include <stdio.h>
#include "list.h"
#include "list_opt.h"

int main() {
    int i = 0;
    list_t *list = new_list_node(0);

    for(i = 0; i < 15; i++){
        list = list_add(list, i + 1);
    }
    printf("初始完整链表数据\n");
    list_print(list);
    list_t *node = get_last_k_node(list, 3); //找到倒数第3个结点
    if(node != NULL){
        printf("倒数第3个结点的值是：%d\n", node->data);
    }else{
        printf("k值不正确找不到目标结点\n");
    }

    list = convert_list(list); //翻转链表
    printf("链表翻转后的数据\n");
    list_print(list);

    list = transfer_to_ring_list(list); //将单链表转成环形链表
    bool have_ring = is_there_a_ring(list); //判断链表是否有环
    if(have_ring){
        printf("链表有环\n");
    }else{
        printf("链表无环\n");
    }

    printf("新建无环链表\n");
    list_t *list2 = new_list_node(20);
    for(i = 0; i < 5; i++){
        list2 = list_add(list2, i + 21);
    }
    have_ring = is_there_a_ring(list2); //判断链表是否有环
    if(have_ring){
        printf("链表有环\n");
    }else{
        printf("链表无环\n");
    }

    return 0;
}

编译运行输出：

初始完整链表数据
15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 
倒数第3个结点的值是：2
链表翻转后的数据
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 
链表有环
新建无环链表
链表无环

代码运行正确。