面试之链表

墨蓝 2023-01-10 11:50 114阅读 0赞

![7ec3308f59dcaf2209718c6866c889dd.png][]

#### 前言 ####

--------------------

这一篇博客是很早之前写的，是关于一些链表和二叉树面试相关的问题，算是整理吧，网上这部分的答案也很多，希望能给大家一些帮助。

###### 注意:本文中一些异常情况都是没有做处理的,例如NULL等等,只是给出了基本的解决方案.大家参考一下. ######

### 链表部分 ###

--------------------

**问题:定义并且创建一个链表.**

解题方案:  
我们首先要如何定义一个结构体,下面的构造方案我是使用的递归的形式来构造一个结构体,注意不要忘记分配内存.其他的方面都比较简单,难度较低.

代码示例:

#include <stdio.h>
    
    typedef struct ListNode {
        int data;
        struct ListNode*nextNode;
    }ListNode;
    
    ListNode* createListNodeAction(int *listArray, int index, int length) {
        ListNode *listNode = (ListNode *) malloc(sizeof (ListNode) );
        ListNode *nextNode = NULL;
        int i = listArray[index];
        listNode->data = i;
        if (index != length - 1) {
            nextNode = (ListNode*) malloc(sizeof (ListNode));
            nextNode = createListNodeAction(listArray, index + 1, length);
        }
        listNode->nextNode = nextNode;
        return listNode;
    }

--------------------

**问题:不通过遍历删除链表中的非尾节点.**

解题方案:  
首先我们要知道我们如何通过遍历删除链表中的某个节点? 通过遍历我们可以知道要删除的链表节点前驱(也就是前一个节点),然后我们把前驱的nextNode指向要删除的节点的nextNode,释放要删除的节点即可.示意图如下所示.

![260e280f19710b41efef19bd1954c897.png][]

那么我们对于上面的那个题目,我们该如何解决呢?由于前驱不通过遍历我们是拿不到的,所以我们只能通过覆盖的形式,用nextNode节点的属性覆盖掉需要删除的节点,然后释放nextNode节点,这样就完成了删除工作,由于前驱的nextNode指针属性不通过遍历修改不了,所以不能删除尾节点.否则就会有野指针问题出现.

代码示例:

void deleteListNodeNotTail(ListNode *deleteNode) {
      
        ListNode *deleteNextNode = deleteNode->nextNode;
        deleteNode->data = deleteNextNode->data;
        deleteNode->nextNode = deleteNextNode->nextNode;
        free(deleteNextNode);
    }

--------------------

**问题:只遍历一次就找到链表中的中间节点.**

解题方案:  
撇开题目不谈,我们首先要清楚如何确定链表中的中间节点?由于链表没有长度的属性,所以暴力法的做法就是先遍历一次确定链表的长度,然后再次遍历链表找到中间节点.时间复杂度为O(logn+n).

那么如何通过一次遍历来找到链表中的中间节点呢?我们的解决方案是我们需要一快一慢两个移动节点**fathNode**和**slowNode**,**fathNode**的偏移速度是**slowNode**的两倍,所以当**fathNode** == NULL,**slowNode**正好处于中心节点上.时间复杂度为O(logn).

代码示例:

ListNode* getListHalfNode(ListNode *listNode) {
        
        ListNode *fathNode = listNode->nextNode;
        ListNode *slowNode = listNode;
    
        while (fathNode) {
            fathNode = fathNode->nextNode->nextNode;
            slowNode = slowNode->nextNode;
        }
        return slowNode;
    }

--------------------

**问题:如何找到单向链表中的倒数第i个节点(i >= 1).**

解题方案:  
暴力法该如何解决这种问题呢?我们先遍历一遍确定链表的长度length,再次遍历链表取得下标位置在length-1-k的节点就是我们要的节点.时间复杂度为O(logn+n).

那没有有没有优化方式呢?这是有的,仍然借助上一个问题的解决方案,我们需要一快一慢两个移动节点**fathNode**和**slowNode**,**fathNode**先偏移i个位置,然后两个节点同时进行移动,所以当**fathNode** == NULL,**slowNode**正好处于倒数.时间复杂度为O(2logn).

代码示例:

ListNode* getListNodeWithLast(ListNode *listNode,int i) {
        
        ListNode *fathNode = listNode;
        ListNode *slowNode = listNode;
        
        while (i) {
            fathNode = fathNode->nextNode;
            i--;
        }
        
        while (fathNode) {
            fathNode = fathNode->nextNode;
            slowNode = slowNode->nextNode;
        }
        return slowNode;
    }

--------------------

**问题:删除倒数第i个结点(i>=1),不能用替换删除法.**

解题方案:  
上面我们已经了解了替换删除法,不需要知道前驱,我们就可以使用覆盖替换的方式删除节点,而这次我们可以是知道前驱节点的,而且结合上一次的快慢节点的方式,我们只需要先找到前驱节点即可.也就是**fathNode**节点需要先移动**i + 1** 次,具体代码如下所示.

代码示例:

void deleteListNodeWithLast(ListNode *listNode,int i) {
        
        ListNode *fathNode = listNode;
        ListNode *slowNode = listNode;
        
        while (i + 1) {
            fathNode = fathNode->nextNode;
            i--;
        }
        
        while (fathNode) {
            fathNode = fathNode->nextNode;
            slowNode = slowNode->nextNode;
        }
        
        ListNode *deleteNode = slowNode->nextNode;
        ListNode *deleteNextNode = deleteNode->nextNode;
        slowNode->nextNode = deleteNextNode;
        free(deleteNode);
    }

--------------------

**问题:约瑟夫问题**

约瑟夫环(约瑟夫问题)是一个数学的应用问题：已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。

解题方案:  
使用链表该如何解决约瑟夫问题呢?我们需要把链表做成一个环,也就是我们需要遍历一遍找到尾节点,并且制定尾节点的nextNode指针指向链表的第一个节点,这样我们就把链表做成了一个环.

然后我们假设每**i**次删除一个节点,这样返回的删除,直到只剩最后一个节点就是我们要求的解.

代码示例:

ListNode* JocephCircle(ListNode *firstNode, int k) {
        
        ListNode *endNode = firstNode;
        ListNode *resultNode = firstNode;
        ListNode *deleteNode = NULL;
        
        // 做环
        while (endNode->nextNode) {
            endNode = endNode->nextNode;
        }
        endNode->nextNode = firstNode;
    
        // 自身的nextNode指向自身的时候,就只剩下一个元素了
        while (resultNode->nextNode != resultNode) {
            
            //删除节点 ,先找到前驱节点,然后找到删除节点
            //由于先执行赋值操作,再进行i-1操作,所以k-1,由于是找删除节点的前驱节点,所以还需要-1.
            int i = (k-1)-1;
            while (i) {
                resultNode = resultNode->nextNode;
                i--;
            }
            
            // 重新指向并且释放删除节点
            deleteNode = resultNode->nextNode;
            resultNode->nextNode = resultNode->nextNode->nextNode;
            free(deleteNode);
            resultNode = resultNode->nextNode;
        }
        
        return resultNode;
    }

--------------------

**问题:单链表的冒泡排序问题**

解题方案:  
仿照普通的数组遍历,这里两个while进行实现简单的冒泡排序.判断条件为nextNode节点是否为NULL,即可知道是否已经到达了单链表的尾节点.这个问题如果不做任何优化的话就如同下面代码演示的即可.其他优化方式就不过多阐述,上网查询即可.

代码示例:

void sortNodeListAction(ListNode *firstNode) {
     
        ListNode *nowNode = firstNode;
        ListNode *exchangeNode = (ListNode *)malloc(sizeof(ListNode));
        
        while (nowNode->nextNode) {
            ListNode *nowNextNode = nowNode;
            while (nowNextNode) {
                if (nowNextNode->data < nowNode->data) {
                    exchangeNode->data = nowNextNode->data;
                    nowNextNode->data = nowNode->data;
                    nowNode->data = exchangeNode->data;
                }
                nowNextNode = nowNextNode->nextNode;
                if (!nowNextNode) {
                    continue;
                }
            }
            nowNode = nowNode->nextNode;
        }
        free(exchangeNode);
    }

--------------------

**问题:判断链表是否带环；若带环，求环的长度和入口点**

解题方案:  
这里我们要首先明白什么叫做带环,如下图所示,不管是哪种表现形式,我们都说当前链表是带环的链表.

![7bb4b1b1e41cba3d453421ebefba21c2.png][]

我们了解了什么叫链表带环.在代码中,我们该如何判断当前的链表是否带环呢?网上有一种方案就是使用快慢节点解决,设置**fathNode**和**slowNode**,**fathNode**的偏移速度是**slowNode**的两倍,所以当**fathNode** == NULL,那么可以断定链表不带环,假设在某一个时刻**fathNode**==**slowNode**,说明两个节点重合,也就是说链表带环.

那么带环的链表我们该如何判断其环的长度呢?首先我们要知道**fathNode**偏移速度是**slowNode**的两倍,也就是说相同时间内,**fathNode**偏移距离是**slowNode**的**2**倍.

我们要说明两个节点交汇的情况,两者的情况肯定是慢节点在换上走不到一圈就会进行交汇,有人会问这是为什么呢?因为**fathNode**偏移速度是**slowNode**的两倍,所以在两者起点相同的情况下**slowNode**走完一圈**fathNode**走完两圈内,两者是必然相交的.

根据上面的两种情形,如下图所示.当两点相交时,我们有以下的结论,**fathNode**走过的路程为L + (C + A) + A,**slowNode**走过的路程为L + A, 我们得出 (L + A) x 2 = L + (C + A) + A;所以L = C.这时候我们继续定义一个新的节点**enterNode**从头开始出发,**slowNode**同时出发,两者速度相同,同时L = C;所以我们知道两者相交的节点必然是环的入口点.这时候**enterNode**再走到b点,就可以计算出环的长度了.

![6eef67ac07676db97dad6e6f84cf9bdd.png][]

代码示例:

// 判断是否有环
    bool isExistLoop(ListNode* firstNode)  {  
        ListNode *fastNode;
        ListNode * slowNode;
        fastNode = slowNode = firstNode;
        while (slowNode != NULL && fastNode -> next != NULL)  {  
            slowNode = slowNode -> next ;
            fastNode = fastNode -> next -> next ; 
            if (slowNode == fastNode) 
                return true ;  
        }  
        return false ;  
    }

// 判断环的长度
    int getLoopLength(ListNode* firstNode){
        ListNode* slowNode = firstNode;
        ListNode* fastNode = firstNode;
        while ( fastNode && fastNode ->next ){
            slowNode = slowNode->next;
            fastNode = fastNode->next->next;
            if ( slowNode== fastNode) {
                break;
             }
        }
        slowNode= slowNode->next;
        fastNode = fastNode->next->next;
        int length = 1; 
        while ( fastNode != slowNode)
        {
            slowNode = slowNode->next;
            fastNode = fastNode->next->next;
            length ++; 
        }
        return length;
    }

// 找到环中的相遇节点
    ListNode* getMeetingNode(ListNode* firstNode) {
        ListNode* fastNode;
        ListNode* slowNode;
        slowNode = fastNode = firstNode;
        while (slowNode != NULL && fastNode-> next != NULL) {  
            slowNode = slowNode-> next ;
            fastNode = fastNode-> next -> next ;
            if (slowNode == fastNode)
                return slowNode;  
        }  
    
        //到达末尾仍然没有相遇，则不存在环
        return NULL ;
    }
    // 找出环的入口节点
    ListNode* getEntryNodeOfLoop(ListNode* firstNode) {
        ListNode* meetingNode = getMeetingNode(firstNode); // 先找出环中的相遇节点
        if (meetingNode == NULL)
            return NULL;
        ListNode* p1 = meetingNode;
        ListNode* p2 = pHead;
        while (p1 != p2) {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }

如果可以使用字典或者集合的话,那就更简单了;数组也是可以解决,但是效率不是太高.需要多次遍历.

--------------------

#### 总结 ####

--------------------

OK,写到这里基本上就结束了，先整理这些后期会持续更新，欢迎大家指导批评，谢谢。。。

![1cc773b3510614b54c92ffc3dc40d24a.gif][]

[7ec3308f59dcaf2209718c6866c889dd.png]: /images/20221119/0c75473259d6430da6aba920b4fc76c6.png
[260e280f19710b41efef19bd1954c897.png]: https://img-blog.csdnimg.cn/img_convert/260e280f19710b41efef19bd1954c897.png
[7bb4b1b1e41cba3d453421ebefba21c2.png]: https://img-blog.csdnimg.cn/img_convert/7bb4b1b1e41cba3d453421ebefba21c2.png
[6eef67ac07676db97dad6e6f84cf9bdd.png]: https://img-blog.csdnimg.cn/img_convert/6eef67ac07676db97dad6e6f84cf9bdd.png
[1cc773b3510614b54c92ffc3dc40d24a.gif]: https://img-blog.csdnimg.cn/img_convert/1cc773b3510614b54c92ffc3dc40d24a.gif