前言
这一篇博客是很早之前写的，是关于一些链表和二叉树面试相关的问题，算是整理吧，网上这部分的答案也很多，希望能给大家一些帮助。
注意:本文中一些异常情况都是没有做处理的,例如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,写到这里基本上就结束了，先整理这些后期会持续更新，欢迎大家指导批评，谢谢。。。
网友评论