企业淘宝网站备案,博客类网站建设,建筑设计自学网站,做视频网站版权怎么解决单链表经典算法专题 一、 单链表相关经典算法OJ题1#xff1a;移除链表元素 解法一#xff1a;在原链表中删除Node.nextnext的节点 typedef struct ListNode ListNode;
struct ListNode* removeElements( ListNode* head, int val) {ListNode* pcur head;ListNode* pre h…单链表经典算法专题 一、 单链表相关经典算法OJ题1移除链表元素 解法一在原链表中删除Node.nextnext的节点 typedef struct ListNode ListNode;
struct ListNode* removeElements( ListNode* head, int val) {ListNode* pcur head;ListNode* pre head;while (pcur){while (pcur-val ! val ){pre pcur;pcur pcur-next;if (pcur NULL){return head;}}if (head-val val){head head-next;pcur head;pre head;}else if (pcur-val val){pcur pcur-next;pre-next pcur;}}return head;
} 注意:当头节点的valval时要改变头节点的位置 解法二创建新的指向头尾的链表 typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val){ListNode * newHeadNULL;ListNode * newTailNULL;ListNode* pcurhead;while(pcur){if(pcur-val!val){if(newHeadNULL){newHeadpcur;//注意这里不能写headnewTailpcur;}else {newTail-nextpcur;newTailnewTail-next;}}pcurpcur-next;}if(newTail){newTail-nextNULL;}return newHead;} 注意这里如果写head的话当一个节点是要删除的节点头节点还是那个删除的节点。 二、单链表相关经典算法OJ题2反转链表 解法一创建新链表对新链表进行头插 typedef struct ListNode SLNode;
struct ListNode* reverseList(struct ListNode* head){SLNode* newHead NULL;SLNode* newTail NULL;SLNode* pcur head;SLNode* last head;while (head!NULL){if (newHead NULL){newHead newTail head;head head-next;}else{last head;head head-next;pcur last;pcur-next newHead;newHead pcur;}}if (newTail!NULL){newTail-next NULL;}return newHead;} 解法二定义三个变量n1,n2,n3(n1,n2用来反转指向n3在前面遍历 typedef struct ListNode ListNode;
struct ListNode* reverseList( ListNode* head) {if(headNULL){return NULL;}ListNode * n1NULL;ListNode * n2head;ListNode * n3head-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3){n3n3-next;}}return n1;
} 三、 单链表相关经典算法OJ题3合并两个有序链表 解法一在原链表基础上进行修改会使用到指定位置之前插入数 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if (list1 NULL){return list2;}if (list2 NULL){return list1;}ListNode* pcur1 list1;ListNode* pre list1;ListNode* pcur2 list2;ListNode* pcur3 list2-next;while (pcur1 pcur2){while (pcur1-val pcur2-val){pre pcur1;pcur1 pcur1-next;if (pcur1 NULL){pre-next pcur2;return list1;}}if (list1-val pcur2-val){pcur2-next list1;list1 pcur2;pre list1;pcur2 pcur3;if (pcur3 ! NULL){pcur3 pcur3-next;}}//在pur1实现头插else{pre-next pcur2;pcur2-next pcur1;pcur2 pcur3;if (pcur3 ! NULL){pcur3 pcur3-next;}}}return list1;
} 输出结果 解法二创建一个新的空链表遍历俩个链表进行新链表的尾插
使用单链表无头单向不循环链表 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if (list1 NULL){return list2;}if (list2 NULL){return list1;}ListNode* newheadNULL;ListNode* newtailNULL;ListNode* pcur1list1;ListNode* pcur2list2;while(pcur1pcur2){if(pcur1-valpcur2-val){if(newheadNULL)//插入新链表{newheadnewtailpcur1;}else{newtail-nextpcur1;newtailnewtail-next;}pcur1pcur1-next;}else{if(newheadNULL)//插入新链表{newheadnewtailpcur2;}else{newtail-nextpcur2;newtailnewtail-next;}pcur2pcur2-next;}}if(pcur1NULL){newtail-nextpcur2;}if(pcur2NULL){newtail-nextpcur1;}return newhead;
}
优化解法二使用带头单向不循环链表
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if (list1 NULL){return list2;}if (list2 NULL){return list1;}ListNode* newhead,*newtail;newhead newtail(ListNode*)malloc(sizeof(ListNode));ListNode* pcur1list1;ListNode* pcur2list2;while(pcur1pcur2){if(pcur1-valpcur2-val){//直接插入新链表newtail-nextpcur1;newtailnewtail-next;pcur1pcur1-next;}else{newtail-nextpcur2;newtailnewtail-next;pcur2pcur2-next;}}if(pcur1NULL){newtail-nextpcur2;}if(pcur2NULL){newtail-nextpcur1;}ListNode * retheadnewhead-next;free(newhead);newheadNULL;return rethead;;
} 注相比较与不带头链表带头链表省略了反复判断头节点是否为空直接插入头的后面,所带的头不带任何数据,所以返回的时候返回头的next. 四、单链表相关经典算法OJ题4链表的中间结点 解法一使用快慢指针
//快慢指针
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head){if(headNULL){return NULL;}ListNode * slow,*fast;slowhead;fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}return slow;} 注这种快慢指针可以运用到寻找单链表的倒数第几个节点比如说找倒数第3个节点只需要让慢指针与快指针相差3个节点当快指针走到NULL,此时慢指针为倒数第3个节点。 还有一点值得注意的是 while(fastfast-next)该位置判断不能颠倒因为可能fast为空此时先判断fast-next会报错。 五、 循环链表经典应⽤-环形链表的约瑟夫问题 著名的Josephus问题 据说著名犹太 历史学家 Josephus有过以下的故事在罗⻢⼈占领乔塔帕特后39 个犹太⼈与 Josephus及他的朋友躲到⼀个洞中39个犹太⼈决定宁愿死也不要被⼈抓到于是决定了⼀个⾃杀 ⽅式41个⼈排成⼀个圆圈由第1个⼈开始报数每报数到第3⼈该⼈就必须⾃杀然后再由下⼀ 个重新报数直到所有⼈都⾃杀⾝亡为⽌。 然⽽Josephus 和他的朋友并不想遵从Josephus要他的朋友先假装遵从他将朋友与⾃⼰安排在第16个与第31个位置于是逃过了这场死亡游戏。 解法一创建一个单向循环链表遇到计数等于m的节点删除剩下最后一个节点的val值即为所求编号
typedef struct ListNode ListNode;
ListNode * SLbuyNode(int x)//创造一个节点
{ListNode * Node(ListNode*)malloc(sizeof(ListNode));Node-valx;Node-next NULL;return Node;
}
//创建一个循环链表
ListNode *CreatSLNode(int n)
{ListNode * headSLbuyNode(1);ListNode * tailhead;for(int i2;in;i){tail-nextSLbuyNode(i);tailtail-next;}tail-nexthead;return tail;
}int ysf(int n, int m ) {ListNode* prevCreatSLNode(n);ListNode* pcurprev-next;int count1;while(pcur-next!pcur){if(countm)//报到m的节点删除{prev-nextpcur-next;free(pcur);pcurprev-next;count1;}else //没报m继续往前走{prevpcur;pcurpcur-next;count;}}return pcur-val;
} 注意红框若改成SLbuyNode(1),表示tail又重新开辟一块空间和head不是同一片空间所以连不起来。 六、 单链表相关经典算法OJ题5分割链表 解法一创建俩个带头单向不循环链表将大于等于x和小于x的节点分别放入俩个空链表然后小链表和大链表头尾相接
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){if(headNULL){return NULL;}ListNode * maxhead,*maxtail;ListNode * minhead,*mintail;maxhead maxtail(ListNode*)malloc(sizeof(ListNode));minheadmintail(ListNode*)malloc(sizeof(ListNode));ListNode *pcurhead;while(pcur){if(pcur-valx){mintail-nextpcur;mintailmintail-next;pcurpcur-next;}else{maxtail-nextpcur;maxtailmaxtail-next;pcurpcur-next;}}if(maxtail-next!NULL){maxtail-nextNULL;}mintail-nextmaxhead-next;ListNode*ret minhead-next;free(maxhead);maxheadNULL;free(minhead);minheadNULL;return ret;
}
