面试之链表

前言
这一篇博客是很早之前写的，是关于一些链表和二叉树面试相关的问题，算是整理吧，网上这部分的答案也很多，希望能给大家一些帮助。
注意:本文中一些异常情况都是没有做处理的,例如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,释放要删除的节点即可.示意图如下所示.

那么我们对于上面的那个题目,我们该如何解决呢?由于前驱不通过遍历我们是拿不到的,所以我们只能通过覆盖的形式,用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);
}

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

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

我们了解了什么叫链表带环.在代码中,我们该如何判断当前的链表是否带环呢?网上有一种方案就是使用快慢节点解决,设置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点,就可以计算出环的长度了.

代码示例:

// 判断是否有环
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,写到这里基本上就结束了，先整理这些后期会持续更新，欢迎大家指导批评，谢谢。。。

转自：https://www.jianshu.com/p/cf89d05c8f30