【41期】盘点那些必问的数据结构算法题之链表

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 【41期】盘点那些必问的数据结构算法题之链表

点击上方“Java面试题精选”,关注公众号

面试刷图,查缺补漏

号外:****往期面试题,10篇为一个单位归置到本公众号菜单栏-面试题,有需要的欢迎翻阅。

0 概述

链表作为一种基础的数据结构,在很多地方会用到。如在Linux内核代码,redis源码,python源码中都有使用。除了单向链表,还有双向链表,本文主要关注单向链表(含部分循环链表题目,会在题目中注明,其他情况都是讨论简单的单向链表)。双向链表在redis中有很好的实现,也在我的仓库中拷贝了一份用于测试用,本文的相关代码在 这里。

https://github.com/shishujuan/data-structure-algorithms

1 定义

先定义一个单向链表结构,如下,定义了链表结点和链表两个结构体。这里我没有多定义一个链表的结构体,保存头指针,尾指针,链表长度等信息,目的也是为了多练习下指针的操作。


// aslist.h

// 链表结点定义
typedef struct ListNode {
    struct ListNode *next;
    int value;
} listNode;

【41期】盘点那些必问的数据结构算法题之链表

2 基本操作

在上一节的链表定义基础上,我们完成几个基本操作函数,包括链表初始化,链表中添加结点,链表中删除结点等。


/**
 * 创建链表结点
 */
ListNode *listNewNode(int value)
{
    ListNode *node;
    if (!(node = malloc(sizeof(ListNode))))
        return NULL;

    node-value = value;
    node-next = NULL;
    return node;
}

/**
 * 头插法插入结点。
 */
ListNode *listAddNodeHead(ListNode *head, int value)
{
    ListNode *node;
    if (!(node = listNewNode(value)))
        return NULL;

    if (head) 
        node-next = head;

    head = node;
    return head;
}

/**
 * 尾插法插入值为value的结点。
 */
ListNode *listAddNodeTail(ListNode *head, int value)
{
    ListNode *node;
    if (!(node = listNewNode(value)))
        return NULL;

    return listAddNodeTailWithNode(head, node);
}

/**
 * 尾插法插入结点。
 */
ListNode *listAddNodeTailWithNode(ListNode *head, ListNode *node)
{
    if (!head) {
        head = node;
    } else {
        ListNode *current = head;
        while (current-next) {
            current = current-next;
        } 
        current-next = node;
    }
    return head;
}

/**
 * 从链表删除值为value的结点。
 */
ListNode *listDelNode(ListNode *head, int value)
{
    ListNode *current=head, *prev=NULL;

    while (current) {
        if (current-value == value) {
            if (current == head)
                head = head-next;

            if (prev)
                prev-next = current-next;

            free(current);
            break;
        }

        prev = current;
        current = current-next;
    }
    return head;
}

/**
 * 链表遍历。
 */
void listTraverse(ListNode *head)
{
    ListNode *current = head;
    while (current) {
        printf("%d", current-value);
        printf("-");
        current = current-next;
        if (current == head) // 处理首尾循环链表情况
            break;
    }

    printf("NULLn");
}

/**
 * 使用数组初始化一个链表,共len个元素。
 */
ListNode *listCreate(int a[], int len)
{
    ListNode *head = NULL;
    int i;
    for (i = 0; i  len; i++) {
        if (!(head = listAddNodeTail(head, a[i])))
            return NULL;
    }
    return head;
}

/**
* 链表长度函数
*/
int listLength(ListNode *head)
{
    int len = 0;
    while (head) {
        len++;
        head = head-next;
    }
    return len;
}

3 链表相关面试题

3.1 链表逆序

题:** 给定一个单向链表 1-2-3-NULL,逆序后变成 3-2-1-NULL。**

解:常见的是用的循环方式对各个结点逆序连接,如下:


/**
 * 链表逆序,非递归实现。
*/
ListNode *listReverse(ListNode *head)
{
    ListNode *newHead = NULL, *current = head;
    while (current) {
        ListNode *next = current-next;
        current-next = newHead;
        newHead = current;
        current = next;
    }

    return newHead;
}

如果带点炫技性质的,那就来个递归的解法,如下:


/**
 * 链表逆序,递归实现。
 */
ListNode *listReverseRecursive(ListNode *head)
{
    if (!head || !head-next) {
        return head;
    }

    ListNode *reversedHead = listReverseRecursive(head-next);
    head-next-next = head;
    head-next = NULL;
    return reversedHead;
}

3.2 链表复制

题:** 给定一个单向链表,复制并返回新的链表头结点。**

解:同样可以有两种解法,非递归和递归的,如下:


/**
 * 链表复制-非递归
 */
ListNode *listCopy(ListNode *head) 
{
    ListNode *current = head, *newHead = NULL, *newTail = NULL; 
    while (current) {
        ListNode *node = listNewNode(current-value);
        if (!newHead) { // 第一个结点
            newHead = newTail = node;
        } else {
            newTail-next = node;
            newTail = node;
        }
        current = current-next;
    }
    return newHead;
}

/**
 * 链表复制-递归
 */
ListNode *listCopyRecursive(ListNode *head)
{
    if (!head) 
        return NULL;

    ListNode *newHead = listNewNode(head-value);
    newHead-next = listCopyRecursive(head-next);
    return newHead;
}

3.3 链表合并

题:** 已知两个有序单向链表,请合并这两个链表,使得合并后的链表仍然有序(注:这两个链表没有公共结点,即不交叉)。如链表1是 1-3-4-NULL,链表2是 2-5-6-7-8-NULL,则合并后的链表为 1-2-3-4-5-6-7-8-NULL。**

解:这个很类似归并排序的最后一步,将两个有序链表合并到一起即可。使用2个指针分别遍历两个链表,将较小值结点归并到结果链表中。如果一个链表归并结束后另一个链表还有结点,则把另一个链表剩下部分加入到结果链表的尾部。代码如下所示:


/**
 * 链表合并-非递归
 */
ListNode *listMerge(ListNode *list1, ListNode *list2)
{
    ListNode dummy; // 使用空结点保存合并链表
    ListNode *tail = &dummy;

    if (!list1)
        return list2;

    if (!list2)
        return list1;

    while (list1 && list2) {
        if (list1-value = list2-value) {
            tail-next = list1;
            tail = list1;
            list1 = list1-next;
        } else {
            tail-next = list2;
            tail = list2;
            list2 = list2-next;
        }
    }

    if (list1) {
        tail-next = list1;
    } else if (list2) {
        tail-next = list2;
    }

    return dummy.next;
}

当然,要实现一个递归的也不难,代码如下:


ListNode *listMergeRecursive(ListNode *list1, ListNode *list2)
{
    ListNode *result = NULL;

    if (!list1)
        return list2;

    if (!list2)
        return list1;

    if (list1-value = list2-value) {
        result = list1;
        result-next = listMergeRecursive(list1-next, list2);
    } else {
        result = list2;
        result-next = listMergeRecursive(list1, list2-next);
    }

    return result;
}

3.4 链表相交判断

题:** 已知两个单向链表list1,list2,判断两个链表是否相交。**如果相交,请找出相交的结点。

解1:可以直接遍历list1,然后依次判断list1每个结点是否在list2中,但是这个解法的复杂度为 O(length(list1) * length(list2))。当然我们可以遍历list1时,使用哈希表存储list1的结点,这样再遍历list2即可判断了,时间复杂度为O(length(list1) + length(list2)),空间复杂度为 O(length(list1)),这样相交的结点自然也就找出来了。当然,找相交结点还有更好的方法。

解2:两个链表如果相交,那么它们从相交后的节点一定都是相同的。假定list1长度为len1,list2长度为len2,且 len1 len2,则我们只需要将 list1 先遍历 len1-len2个结点,然后两个结点一起遍历,如果遇到相等结点,则该结点就是第一个相交结点。


/**
 * 链表相交判断,如果相交返回相交的结点,否则返回NULL。
 */
ListNode *listIntersect(ListNode *list1, ListNode *list2)
{
    int len1 = listLength(list1);
    int len2 = listLength(list2);
    int delta = abs(len1 - len2);

    ListNode *longList = list1, *shortList = list2;

    if (len1  len2) {
        longList = list2;
        shortList = list1;
    }

    int i;
    for (i = 0; i  delta; i++) {
        longList = longList-next;
    }

    while (longList && shortList) {
        if (longList == shortList)
            return longList;

        longList = longList-next;
        shortList = shortList-next;
    }

    return NULL;
}

3.5 判断链表是否存在环

题:** 给定一个链表,判断链表中是否存在环。**

【41期】盘点那些必问的数据结构算法题之链表

解1:容易想到的方法就是使用一个哈希表记录出现过的结点,遍历链表,如果一个结点重复出现,则表示该链表存在环。如果不用哈希表,也可以在链表结点 ListNode 结构体中加入一个 visited字段做标记,访问过标记为1,也一样可以检测。由于目前我们还没有实现一个哈希表,这个方法代码后面再加。

解2:更好的一种方法是 Floyd判圈算法,该算法最早由罗伯特.弗洛伊德发明。通过使用两个指针fast和slow遍历链表,fast指针每次走两步,slow指针每次走一步,如果fast和slow相遇,则表示存在环,否则不存在环。(注意,如果链表只有一个节点且没有环,不会进入while循环)


/**
 * 检测链表是否有环-Flod判圈算法
 * 若存在环,返回相遇结点,否则返回NULL
 */
ListNode *listDetectLoop(ListNode *head)
{
    ListNode *slow, *fast;
    slow = fast = head;

    while (slow && fast && fast-next) {
        slow = slow-next;
        fast = fast-next-next;
        if (slow == fast) {
            printf("Found Loopn");
            return slow;
        }
    }

    printf("No Loopn");
    return NULL;
}

void testListDetectLoop()
{
    printf("nTestListDetectLoopn");
    int a[] = {1, 2, 3, 4};
    ListNode *head = listCreate(a, ALEN(a));
    listDetectLoop(head);

    // 构造一个环
    head-next-next-next = head;
    listDetectLoop(head);
}

扩展:检测到有环的话,那要如何找链表的环的入口点呢?

首先,我们来证明一下为什么上面的解2提到的算法是正确的。如果链表不存在环,因为快指针每次走2步,必然会比慢指针先到达链表尾部,不会相遇。

如果存在环,假定快慢指针经过s次循环后相遇,则此时快指针走的距离为 2s,慢指针走的距离为 s,假定环内结点数为r,则要相遇则必须满足下面条件,即相遇时次数满足 s = nr。即从起点之后下一次相遇需要循环 r 次。


2s - s = nr = s = nr

环长度r=4,则从起点后下一次相遇需要经过4次循环。

那么环的入口点怎么找呢?前面已经可知道第一次相遇要循环 r 次,而相遇时慢指针走的距离为 s=r,设链表总长度为L,链表头到环入口的距离为a,环入口到相遇点的距离为x,则L = a + r,可以推导出 a = (L-x-a),其中L-x-a为相遇点到环入口点的距离,即链表头到环入口的距离a等于相遇点到环入口距离。


s = r = a + x = a + x = (L-a) = a = L-x-a

于是,在判断链表存在环后,从相遇点和头结点分别开始遍历,两个指针每次都走一步,当两个指针相等时,就是环的入口点。


/**
 * 查找链表中环入口
 */
ListNode *findLoopNode(ListNode *head)
{
    ListNode *meetNode = listDetectLoop(head);
    if (!meetNode)
        return NULL;

    ListNode *headNode = head;
    while (meetNode != headNode) {
        meetNode = meetNode-next;
        headNode = headNode-next;
    }
    return meetNode;
}

3.6 链表模拟加法

题:** 给定两个链表,每个链表的结点值为数字的各位上的数字,试求出两个链表所表示数字的和,并将结果以链表形式返回。假定两个链表分别为list1和list2,list1各个结点值分别为数字513的个位、十位和百位上的数字,同理list2的各个结点值为数字295的各位上的数字。则这两个数相加为808,所以输出按照从个位到百位顺序输出,返回的结果链表如下。**


list1:  (3 - 1 - 5 - NULL)

list2:  (5 - 9 - 2 - NULL)

result: (8 - 0 - 8 - NULL)

解:这个题目比较有意思,需要对链表操作比较熟练。我们考虑两个数字相加过程,从低位到高位依次相加,如果有进位则标记进位标志,直到最高位才终止。设当前位的结点为current,则有:


current-data = list1-data + list2-data + carry
(其中carry为低位的进位,如果有进位为1,否则为0)

非递归代码如下:


/**
 * 链表模拟加法-非递归解法
 */
ListNode *listEnumarateAdd(ListNode *list1, ListNode *list2)
{
    int carry = 0;
    ListNode *result = NULL;

    while (list1 || list2 || carry) {
        int value = carry;
        if (list1) {
            value += list1-value;
            list1 = list1-next;
        }

        if (list2) {
            value += list2-value;
            list2 = list2-next;
        }

        result = listAddNodeTail(result, value % 10);
        carry = ( value = 10 ? 1: 0);
    }

    return result;
}

非递归实现如下:


/**
 * 链表模拟加法-递归解法
 */
ListNode *listEnumarateAddRecursive(ListNode *list1, ListNode *list2, int carry)
{
    if (!list1 && !list2 && carry==0)
        return NULL;

    int value = carry;
    if (list1)
        value += list1-value;

    if (list2)
        value += list2-value;

    ListNode *next1 = list1 ? list1-next : NULL;
    ListNode *next2 = list2 ? list2-next : NULL;
    ListNode *more = listEnumarateAddRecursive(next1, next2, (value = 10 ? 1 : 0));
    ListNode *result = listNewNode(carry);
    result-value = value % 10;
    result-next = more;

    return result;
}

3.7 有序单向循环链表插入结点

题:** 已知一个有序的单向循环链表,插入一个结点,仍保持链表有序,如下图所示。**

【41期】盘点那些必问的数据结构算法题之链表

解:在解决这个问题前,我们先看一个简化版本,就是在一个有序无循环的单向链表中插入结点,仍然保证其有序。这个问题的代码相信多数人都很熟悉,一般都是分两种情况考虑:

  • 如果原来链表为空或者插入的结点值最小,则直接插入该结点并设置为头结点。
  • 如果原来链表非空,则找到第一个大于该结点值的结点,并插入到该结点的前面。如果插入的结点值最大,则插入在尾部。
  • 实现代码如下:

    
    /**
     * 简化版-有序无循环链表插入结点
     */
    ListNode *sortedListAddNode(ListNode *head, int value)
    {
        ListNode *node = listNewNode(value);
        if (!head || head-value = value) { //情况1
            node-next = head;
            head = node;
        } else {  //情况2
            ListNode *current = head;
            while (current-next != NULL && current-next-value  value)
                current = current-next;
            node-next = current-next;
            current-next = node;
        }
        return head;
    }
    

    当然这两种情况也可以一起处理,使用二级指针。如下:

    
    /**
     * 简化版-有序无循环链表插入结点(两种情况一起处理)
     */
    void sortedListAddNodeUnify(ListNode **head, int value)
    {
        ListNode *node = listNewNode(value);
        ListNode **current = head;
        while ((*current) && (*current)-value  value) {
            current = &((*current)-next);
        }
        node-next = *current;
        *current = node;
    }
    

    接下来看循环链表的情况,其实也就是需要考虑下面2点:

    1) prev-value ≤ value ≤ current-value:
    插入到prev和current之间。

    2) value为最大值或者最小值:
    插入到首尾交接处,如果是最小值重新设置head值。

    代码如下:

    
    /**
     * 有序循环链表插入结点
     */
    ListNode *sortedLoopListAddNode(ListNode *head, int value)
    {
        ListNode *node = listNewNode(value);
        ListNode *current = head, *prev = NULL;
        do {
            prev = current;
            current = current-next;
            if (value = prev-value && value = current-value)
                break;
        } while (current != head);
    
        prev-next = node;
        node-next = current;
    
        if (current == head && value  current-value) // 判断是否要设置链表头
            head = node;
    
        return head;
    }
    

    3.8 输出链表倒数第K个结点

    题:** 给定一个简单的单向链表,输出链表的倒数第K个结点。**

    解1:如果是顺数第K个结点,不用多思考,直接遍历即可。这个题目的新意在于它是要输出倒数第K个结点。一个直观的想法是,假定链表长度为L,则倒数第K个结点就是顺数的 L-K+1 个结点。如链表长度为3,倒数第2个,就是顺数的第2个结点。这样需要遍历链表2次,一次求长度,一次找结点。

    
    /**
    * 链表倒数第K个结点-遍历两次算法
    */
    ListNode *getLastKthNodeTwice(ListNode *head, int k)
    {
        int len = listLength(head);     
        if (k  len)
            return NULL;
    
        ListNode *current = head; 
        int i;
        for (i = 0; i  len-k; i++)  //遍历链表,找出第N-K+1个结点
            current = current-next;
    
        return current;
    }
    

    解2:当然更好的一种方法是遍历一次,设置两个指针p1,p2,首先p1和p2都指向head,然后p2向前走k步,这样p1和p2之间就间隔k个节点。最后p1和p2同时向前移动,p2走到链表末尾的时候p1刚好指向倒数第K个结点。代码如下:

    
    /**
    * 链表倒数第K个结点-遍历一次算法
    */
    ListNode *getLastKthNodeOnce(ListNode *head, int k)
    {
        ListNode *p1, *p2;
        p1 = p2 = head;
    
        for(; k  0; k--) {
            if (!p2) // 链表长度不够K
                return NULL;
            p2 = p2-next;
        }
    
        while (p2) {
            p1 = p1-next;
            p2 = p2-next;
        }
        return p1;
    }
    

    参考资料

    https://www.geeksforgeeks.org/detect-loop-in-a-linked-list/ http://www.cppblog.com/humanchao/archive/2008/04/17/47357.html https://www.geeksforgeeks.org/find-first-node-of-loop-in-a-linked-list/ https://www.geeksforgeeks.org/merge-two-sorted-linked-list-without-duplicates/

    来源:juejin.im/post/5b8a0e99f265da43320730ba

    最近三期

    与其在网上拼命找题?** 不如马上关注我们~**

    【41期】盘点那些必问的数据结构算法题之链表

    原文始发于微信公众号(Java面试题精选):

    本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

    转载声明:转载请注明出处,本技术博客是本人原创文章

    本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

    原文链接:blog.ouyangsihai.cn >> 【41期】盘点那些必问的数据结构算法题之链表


     上一篇
    Zookeeper面试23连问,这些你都会吗? Zookeeper面试23连问,这些你都会吗?
    点击上方“后端技术精选”,选择“置顶公众号” 技术文章第一时间送达! 作者:JeffreyLcm segmentfault.com/a/1190000014479433 1.ZooKeeper是什么?ZooKeeper是一个
    2021-04-05
    下一篇 
    【42期】盘点那些必问的数据结构算法题之二叉堆 【42期】盘点那些必问的数据结构算法题之二叉堆
    点击上方“Java面试题精选”,关注公众号 面试刷图,查缺补漏 号外:****往期面试题,10篇为一个单位归置到本公众号菜单栏-面试题,有需要的欢迎翻阅。 0 概述本文要描述的堆是二叉堆。二叉堆是一种数组对象,可以被视为一棵完全二叉树,树中
    2021-04-05