网站功能提升权限,什么页游好玩人多,哪个网站内链建设好,东莞市建设工程交易中心网引导 链表是我们工作和面试的中常常会遇到的知识点#xff0c;只有长时间的练习和思考才能游刃有余。故总结以下几个比较经典的链表题和对应的代码#xff0c;进行参考。
链表的反转
思路#xff1a;
将链表遍历#xff0c;将每个节点拷贝一份#xff0c;之后再将所有的…引导 链表是我们工作和面试的中常常会遇到的知识点只有长时间的练习和思考才能游刃有余。故总结以下几个比较经典的链表题和对应的代码进行参考。
链表的反转
思路
将链表遍历将每个节点拷贝一份之后再将所有的节点反向链接。该方法简单但是我并不喜欢。因为空间复杂度为O(n),时间复杂度也为O(n).利用递归将先遍历到最后节点再返回将每个节点的指向上一个节点。头节点指向null。 #includestdlib.h typedef struct node{ int num; struct node * next; }Node; int insertnode(Node* head,Node* newNode) { if(head NULL) { printf(head is null,insert fail\n); return -1; } Node* temp head; while(temp-next! NULL) { temp temp-next; } temp-next newNode; return 0; } int print_list(Node* head) { while(head!NULL) { printf(%d\n,head-num); head head-next; } return 0; } Node* rollback(Node* head) { Node* temp head-next; Node* newhead NULL; if(temp ! NULL) { newhead rollback(temp); } else { return head; } temp-next head; head-next NULL; return newhead; } int main() { Node * head (Node*)malloc(sizeof(Node)); head-num 1; head-next NULL; int i 0; for(i 2 ; i 5 ; i ) { Node * NewNode (Node*)malloc(sizeof(Node)); NewNode-num i; NewNode-next NULL; insertnode(head,NewNode); } print_list(head); Node* Newhead rollback(head); print_list(Newhead); return 0; }
单向链表中环的检测 该题我觉得可以拓展到以下三个问题
1.检测链表中是否存在环?2.能够求出环的长度?3.能否求出起始点到环入口的长度?
检测链表中是否存在环
思路
使用快慢指针快指针指向NULL时则不存在环若快指针和慢指针重合则说明有环 #includestdlib.h typedef struct node{ int num; struct node * next; }Node; int insertnode(Node* head,Node* newNode) { if(head NULL) { printf(head is null,insert fail\n); return -1; } Node* temp head; while(temp-next! NULL) { temp temp-next; } temp-next newNode; return 0; } int print_list(Node* head) { while(head!NULL) { sleep(1); printf(%d\n,head-num); head head-next; } return 0; } int ring_check(Node* head) { int result -1; Node* fasthead; Node* slowhead; while(fast ! NULL) { if(slow-next ! NULL) slow slow-next; if(fast-next ! NULL fast-next-next ! NULL) fast fast-next-next; else break; if(slow fast) { printf(number %d\n,slow-num); result 1; break; } } return result; } int main() { Node * head (Node*)malloc(sizeof(Node)); head-num 1; head-next NULL; Node * temp NULL; int i 0; for(i 2 ; i 2 ; i ) { Node * NewNode (Node*)malloc(sizeof(Node)); NewNode-num i; NewNode-next NULL; insertnode(head,NewNode); if(i 14)/ *决定环的入口点* / { temp NewNode; } if(i 19) { NewNode-next temp; } } int resulte ring_check(head); //print_list(head); if(resulte 1) { printf(list exist ring\n); } else { printf(list dont exit ring\n); } return 0; }
求出环的长度
思路
建立在问题一的基础之上当第一次相遇之后说明该链表存在环。而快慢指针从一个环中同一点进行移动下一次相遇就是链表的长度。 int ring_len(Node* head) { int first -1; int len 0; Node* fasthead; Node* slowhead; while(fast ! NULL) { if(slow-next ! NULL) slow slow-next; if(fast-next ! NULL fast-next-next ! NULL) fast fast-next-next; else break; if(first 1) len ; if(slow fast) { printf(number %d\n,slow-num); if(first -1) { first 1; } else break; } } return len; }
计算头节点到入口点的距离
思路 依据快指针和慢指针相遇时慢指针肯定还没有超过整个链表长度。而快指针应该是超过链表加上nrn,表示正整数r表示环的长度 现做这样的假设 链表的整个长度是L 头节点到入口点的距离为a 第一次相遇点距离入口点为X并走了s步 得到以下公式2s -s nrxa s 可以得到a (n-1)r (r-x) 其中r-x表示相遇点到入口点的距离。 故从head节点第一次相遇节点分别出发。再次相遇肯定是入口点。 Node* ring_meet(Node* head) { Node* resulte NULL; Node* fasthead; Node* slowhead; while(fast ! NULL) { if(slow-next ! NULL) slow slow-next; if(fast-next ! NULL fast-next-next ! NULL) fast fast-next-next; else return resulte; if(slow fast) { printf(number %d\n,slow-num); break; } } resulte head; int len 0; while(resulte ! slow) { resulte resulte-next; slow slow-next; len; } printf(len %d\n,len); return resulte; }
如何判断两个链表是否相交
该问题其实就是环检测的变种。只要将其中一个链表尾节点指向头节点。再检测另一条链表中是否存在环即可。
两个有序的链表合并
思路
遍历其中一个链表将节点与另一链表进行比较进行插入。 Node * list_merge(Node*L1 , Node*L2) { Node * head (Node*)malloc(sizeof(Node)); Node* cur head; while(L1 ! NULL L2 ! NULL) { if(L1-num L2-num ) { cur-next L1; L1 L1-next; } else { cur-next L2; L2 L2-next; } curcur-next; } if(L1 NULL) { cur-nextL2; } if(L2 NULL) { cur-nextL1; } return head-next; }
删除链表中指定节点
思路
遍历链表当遇到节点相同的便删除对应节点。这样的事件复杂度为O(n)将节点的下一个节点赋值为本节点之后指向node-next-next;这个思路的时间复杂度是O(1)。但是你需要考虑节点的位置在链表头在链表尾在链表中间 int delete_node(Node* head,Node* delete) { if(deleteNULL ) { return 0; } if(delete-next NULL) { / *last node* / while(head-next ! delete) { headhead-next; } head-next NULL; free(delete); return 0; } delete-num delete-next-num; Node * temp delete-next; delete-next delete-next-next; free(temp); return 0; }平均复杂度为O(1)。
求链表中的中间节点
思路:当链表长度为偶数取相邻两个节点的第一个
遍历链表找到尾节点。并记录链表长度。再从头结点遍历达到中间节点即可。这种方式事件复杂度为O(n),空间复杂度O(1)。但感觉太low了并不喜欢。使用快慢指针当快指针达到尾节点时慢节指针肯定是在中间节点 Node* mid_node(Node* head) { if(head NULL) { return NULL; } Node* fasthead; Node* slow head; while(fast-next ! NULL fast-next-next ! NULL) { fastfast-next-next; slowslow-next; } return slow; }
约瑟夫问题
约瑟夫问题是我偶然看到的一个算法题。感觉很有意思就记录下来了。
故事 据说著名犹太历史学家 Josephus有过以下的故事在罗马人占领乔塔帕特后39 个犹太人与Josephus及他的朋友躲到一个洞中39个犹太人决定宁愿死也不要被敌人抓到于是决定了一个自杀方式41个人排成一个圆圈由第1个人开始报数每报数到第3人该人就必须自杀然后再由下一个重新报数直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始越过k-2个人因为第一个人已经被越过并杀掉第k个人。接着再越过k-1个人并杀掉第k个人。这个过程沿着圆圈一直进行直到最终只剩下一个人留下这个人就可以继续活着。问题是给定了和一开始要站在什么地方才能避免被处决Josephus要他的朋友先假装遵从他将朋友与自己安排在第16个与第31个位置于是逃过了这场死亡游戏。 该问题拓展很多这里我给出的问题有100个人每数到3就剔除输出剔除顺序。
例如 123456
输出364251
思路 实现起来应该是很简单的就是有N个节点的环从头节点开始依次数数当数到3时就将节点删除一直重复到只有一个节点。 int Joseph(Node* head) { int i 1; if(head NULL) { printf(list is empty\n); } while(head-next ! head) { i; if(i%3 0) { i1; Node* temp head-next; head-next head-next-next; printf(%d\n,temp-num); free(temp); } headhead-next; } printf(last is %d\n,head-num); }
