wordpress类似的网站,凡科如何开通网站建设,wordpress游戏,做dhl底单的网站是 什么链表的分类
前面我们实现了单链表#xff0c;单链表只是链表的一种。可以根据以下几个标准来判断链表的类型#xff1a;
1.单向或者双向 如图所示#xff0c;单向链表中一个节点的指针域只储存了下一个节点的指针#xff0c;能通过前一个节点访问后一个节点#xff0c;无…链表的分类
前面我们实现了单链表单链表只是链表的一种。可以根据以下几个标准来判断链表的类型
1.单向或者双向 如图所示单向链表中一个节点的指针域只储存了下一个节点的指针能通过前一个节点访问后一个节点无法通过后一个节点访问前一个节点只能实现单向访问。
而双向链表则没有这样的限制双向链表的指针域既有上一个节点的指针又有下一个节点的指针所以双向节点能实现双向访问。
2.带头或者不带头 头节点通常被称为哨兵节点或者头哨兵节点。在链表中哨兵节点是一种特殊的节点通常位于链表的头部或尾部而不存储实际的数据。哨兵节点的作用是简化链表的操作例如插入、删除或遍历等。通过使用哨兵节点可以避免在操作链表时需要特殊处理头部或尾部节点的情况使得代码更加简洁和高效。 3.循环或者不循环 循环链表是一种特殊类型的链表其中最后一个节点指向第一个节点形成一个循环。这意味着在循环链表中没有真正意义上的“尾节点”。所以遍历链表时需要特别注意循环终止条件以避免进入无限循环。
循环链表和不循环链表主要区别在于 结束节点指向 在不循环链表中最后一个节点的指针通常指向空NULL表示链表的结束。而在循环链表中最后一个节点的指针指向第一个节点形成循环。 遍历 在不循环链表中遍历链表时需要检查每个节点的指针是否指向 NULL 来确定结束。而在循环链表中可以定义一个遍历的起点然后遍历整个链表直到返回到起点为止。 插入和删除操作 对于不循环链表插入和删除节点时需要特殊处理最后一个节点。而循环链表中由于没有明确的“尾节点”插入和删除节点相对简单不需要特殊处理尾节点。
循环链表通常用于需要循环访问的场景比如游戏中的循环遍历玩家列表。
总结 根据链表的这几种特性排列组合一共有八种链表类型。一般我们只研究其中两种----单链表单向不带头不循环和双向链表双向带头循环。 链表刷题
1.移除链表元素 思路创建一个新链表遍历原链表找值不为val的值尾插到新链表中。
图解 如果1不为val,尾插到新链表中,newTail更新pcur指向下一个节点 如果2不为val,尾插到新链表中newTail更新pcur指向下一个节点 重复此操作。 代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;struct ListNode* removeElements(struct ListNode* head, int val) {//创建一个空链表ListNode* newHead,*newTail;newHead newTail NULL;//遍历原链表ListNode* pcur head;while(pcur){//找值不为val的值尾插到新链表if(pcur-val ! val){//链表为空if (newHead NULL){newHead newTail pcur;}else{//链表不为空newTail-next pcur;//拿下来的不只是pcur这一个节点拿的是地址后面的一连串节点都拿下来了newTail newTail-next;}} pcur pcur-next; }if(newTail)newTail - next NULL;return newHead;
}
2.反转链表 图解
创建n1,n2,n3三个指针。使n1指向NULLn2指向head。n3指向head-next。
改变n2的指向使n2的next指向n1 使n1指向n2: 使n2指向n3: 使n3指向n3-next 重复上述操作。
代码实现 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;struct ListNode* reverseList(struct ListNode* head) {//判空if (head NULL){return head;}//创建三个指针ListNode* n1,*n2,*n3;n1 NULL;n2 head;n3 head-next;while(n2){n2-next n1;n1 n2;n2 n3;if(n3)n3 n3-next;}return n1;
} 3.链表的中间节点快慢指针的使用 在这里我们要用到快慢指针算法快慢指针算法也称为龟兔赛跑算法是一种用于解决链表相关问题的常用技巧。它通常用于判断链表是否有环以及找到环的起始点。
算法的基本思想使用两个指针一个快指针和一个慢指针它们以不同的速度遍历链表。在遍历过程中快指针每次移动两步慢指针每次移动一步。如果链表中有环那么快指针最终会追上慢指针如果没有环快指针会先到达链表的末尾。通过这种方式可以快速检测出链表是否有环而且还可以找到环的起始点。一旦快指针追上慢指针说明链表中存在环然后可以使用一些技巧来找到环的起始点例如将其中一个指针重新指向链表头部然后两个指针以相同的速度向前移动它们相遇的地方就是环的起始点。快慢指针算法的时间复杂度为 O(n)其中 n 是链表的长度。 在这里我们用来找链表的中间节点可以设置两个指针慢指针一次走一步快指针一次走两步。当快指针遍历完链表时慢指针所在的就是中间节点。当然也可以尝试用这个方法求1/4节点等等。
求中间节点有两种情况节点个数为奇数还是偶数依次来作为循环的条件。
图解
1.奇数个节点 当节点为奇数个时当fast走到尾节点时slow刚好到中间节点所以循环的条件为fast-next ! NULL。
2.偶数个节点 当节点为偶数个时fast走到NULL,slow刚好到后面的一个中间节点所以循环的条件时fast ! NULL;
结合两种情况此题的循环条件为whlie(fast fast-next)。这两个指针都不为NULL的时候进入循环。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head) {//创建快慢指针ListNode* slow;ListNode* fast;slow fast head;while(fast fast-next)//不能改变fast与fast-next的顺序fast可能为空{slow slow-next;fast fast-next-next;}return slow;
}
4.合并两个有序数组 原来的两个链表就是按升序排列的我们可以创建一个新链表用l1和l2两个指针遍历两个原链表将较小值尾插到新链表中依次循环直到l1或者l2为空。再将非空的另一个链表中的数据尾插到新链表中。
图解 当l1或l2为NULL时把另一个不为NULL的尾插到新链表。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//判空if(list1 NULL){return list2;}if(list2 NULL){return list1;}ListNode* l1 list1;ListNode* l2 list2;//创建新链表ListNode* newHead,*newTail;newHead newTail (ListNode*)malloc(sizeof(ListNode));//哨兵位while(l1 l2){if (l1-val l2-val){newTail-next l1;newTail newTail-next;l1 l1-next;}else{newTail-next l2;newTail newTail-next;l2 l2-next; }}//跳出循环:要么l1为空要么l2为空if (l1 NULL){newTail-next l2; }else{newTail-next l1;}//动态申请的内存要释放ListNode* ret newHead-next;free(newHead);newHead NULL;return ret;
} 5.分割链表 /*
struct ListNode {int val;struct ListNode *next;
};*/
#include csignal
#include cstdlib
typedef struct ListNode ListNode;ListNode* partition(ListNode* head, int x) {//创建两个带头链表ListNode *lessHead,*lessTail;ListNode *greaterHead,*greaterTail;lessHead lessTail (ListNode*)malloc(sizeof(ListNode));greaterHead greaterTail (ListNode*)malloc(sizeof(ListNode));//遍历原链表ListNode* pcur head;if (head NULL)return head;while(pcur){if (pcur-next x){//尾插到小链表lessTail-next pcur;lessTail lessTail-next;}else {greaterTail -next pcur;greaterTail greaterTail-next;}pcur pcur-next}greaterTail-next NULL;//防止死循环 初始化next指针//使小链表的为节点和大链表的第一个有效节点首尾相连lessTail-next greaterHead-next//释放动态申请的内存ListNode* ret lessHead-next;free(lessHead);free(greaterHead);lessHead greaterHead NULL;return ret;}
