《数据结构初阶》【顺序表/链表 精选15道OJ练习】
往期《数据结构初阶》回顾：
【时间复杂度 + 空间复杂度】
【顺序表 + 单链表 + 双向链表】
前言：
“小伙伴们五一快乐呀！✨ 是不是已经闻到了假期阳光的味道？在你们开启度假模式前，先来和我一起解锁这篇技术干货吧~”
前面我们学习了数据结构中的顺序表和链表，现在你是不是苦于不知道如何练习巩固？又或者想刷题却不知从何下手？
别担心！ 博主这里特地准备了 15道经典OJ练习题，涵盖顺序表和链表的各类操作，从基础到进阶，帮你一步步打通任督二脉！💪
🌟 "纸上得来终觉浅，绝知此事要躬行！" 🌟
现在，请深吸一口气，点开第一题——
你离算法大佬，只差15道题的距离！🚀
💪 干就完了，奥利给！
---------------顺序表OJ练习---------------
题目介绍
方法一：
intremoveDuplicates(int* nums,int numsSize){//思路：使用在同一个容器中遍历的快慢指针int fast=0,slow=0;for(;fast<numsSize;fast++){//何时更新慢指针呢？if(nums[fast]!=nums[slow]){ slow++; nums[slow]=nums[fast];}}return slow+1;//slow+1是nums中唯一元素的数量}
题目介绍
方法一：
intremoveElement(int* nums,int numsSize,int val){//思考：空间复杂度O(1)意味着不可以使用额外的空间 ---> 使用遍历同一个容器的快慢指针int fast=0,slow=0;for(;fast<numsSize;fast++){//判断何时让slow指针向后移动if(nums[fast]!=val){ nums[slow]=nums[fast]; slow++;}}return slow;//slow的值就是nums数组中不等于val的元素的数量}
题目介绍
方法一：
voidmerge(int* nums1,int nums1Size,int m,int* nums2,int nums2Size,int n){//思路：使用类似归并排序的最后一步：双路归并（遍历两个容器的三指针）int tmp[n+m];int p1=0,p2=0,pi=0;for(;p1<m&&p2<n;pi++){if(nums1[p1]<=nums2[p2]) tmp[pi]=nums1[p1++];else tmp[pi]=nums2[p2++];}while(p1<m) tmp[pi++]=nums1[p1++];while(p2<n) tmp[pi++]=nums2[p2++];for(int i=0;i<m+n;i++) nums1[i]=tmp[i];return;}
方法二：
voidmerge(int* nums1,int nums1Size,int m,int* nums2,int nums2Size,int n){//思路：从后往前比较两个数组中元素的大小，将大的元素添加到nums1数组的末尾//1.定义三个指针分别指向：// l1 指向 nums1 的最后一个有效元素（m-1）// l2 指向 nums2 的最后一个元素（n-1）// l3 指向 nums1 的最后一个位置（m+n-1）int l1=m-1,l2=n-1;int l3=m+n-1;//2.从后向前进行比较合并，知道其中一个数组中的元素已经遍历完了while(l1>=0&&l2>=0){if(nums1[l1]<nums2[l2]) nums1[l3--]= nums2[l2--];else nums1[l3--]= nums1[l1--];}// 循环结束后有两种情况：//1）l1 >= 0：nums1 中剩余元素已经在正确位置，无需处理//2）l2 >= 0：nums2 中还有剩余元素未合并// 只需要处理第二种情况：将 nums2 剩余元素复制到 nums1 前端while(l2>=0){ nums1[l3--]= nums2[l2--];}return;}
---------------链表OJ练习---------------
题目介绍
方法一：
/** * Definition for singly-linked list. * struct ListNode * { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:intkthToLast(ListNode* head,int k){//思考：如果这道题是返回数组中倒数第K个元素的值，那简直就是小菜一碟//为自己添加额外的条件：//1.空间复杂度O(1) （有人想着将链表中的节点都存到数组中，但是被限制）//2.只能遍历链表一次 （有人想着将链表进行逆序，然后遍历链表直接访问链表的第k个元素）//正确的思路：//1.使用两个相差k个节点距离的指针，然后让两个指针同时走，//2.当在前面的快指针指向空的时候，慢指针指向的节点就是我们想要的答案 ListNode *first=head,*last=head;while(k--){ first=first->next;}//一次遍历整个链表for(;first!=nullptr;){ first=first->next; last=last->next;}return last->val;}};
OR36 链表的回文结构
题目介绍
开始挑战： OR36 链表的回文结构
方法一：
判断链表是否为回文链表 = 反转单向链表
反转单向链表 = 寻找单向链表的中间节点
实现：寻找链表的中间节点
/** * @brief 寻找链表的中间节点（快慢指针法） * @param head 链表头节点指针 * @return 中间节点指针 * * 原理：快指针每次走两步，慢指针每次走一步， * 当快指针到达链表末尾时，慢指针正好在中间。 */ ListNode*middleNode(ListNode* head){ ListNode* slow = head, ListNode* fast = head;while(fast && fast->next){ slow = slow->next; fast = fast->next->next;}return slow;}/* 第一阶段： 1.1：定义快慢指针并其初始化为头指针的指向的位置 第二阶段：使用 while 双步指针遍历整个链表 2.1：慢指针走一步 2.2：快指针走两步 第三阶段：返回慢指针（慢指针指向的中间节点） */
代码片段解释：
while(fast && fast->next)
这个循环条件是快慢指针法寻找链表中间节点的核心安全保证，其精妙之处在于同时防范了两种可能的越界情况：
第一种情况：开始的情况
| 输入情况 | 条件表现 | 结果正确性 |
|---|
| 空链表 | fast初始为null → 不进入循环 | 返回null |
| 单节点链表 | fast->next为null → 不进入循环 | 返回head |
第二种情况：结束的情况
| 检查条件 | 防护场景 | 示例说明 |
|---|
fast != nullptr | 防止访问nullptr->next的非法操作 | 当链表节点数为奇数时，快指针最后停在最后一个节点（fast->next == nullptr） |
fast->next != nullptr | 确保能安全执行fast->next->next | 当链表节点数为偶数时，快指针最后会走到空指针（fast = nullptr） |
示例：具体执行过程分析
情况1：链表长度为奇数（如 1→2→3→4→5）
情况2：链表长度为偶数（如 1→2→3→4→5→6）
总结：无论链表长度奇偶，总能准确找到中间节点（偶数时返回第二个中间节点）
实现：反转单向链表
/** * @brief 反转单向链表（三指针法） * @param head 链表头指针的引用（注意：会修改原始头指针） * @return 反转后的新链表头指针 * * 算法原理： * 使用三个指针协同工作： * 1. newHead：始终指向已反转部分链表的头部 * 2. curr：当前待反转的节点 * 3. next：保存curr原下一个节点的临时指针 * * 时间复杂度：O(n) * 空间复杂度：O(1) */ ListNode*reverseList(ListNode*& head)//参数是头指针的引用（会修改原指针）{ ListNode* next =nullptr; ListNode* newHead =nullptr; ListNode* curr = head;while(curr !=nullptr){ next = curr->next; curr->next = newHead; newHead = curr; curr = next;} head = newHead;return head;}/* 第一阶段：定义三个指针并对其进行初始化 1.1：初始化新链表头为空 1.2：当前节点从原始头节点开始 1.3：用于临时存储下一个节点 第二阶段：使用while循环单步走指针遍历整个链表 2.1：保存当前节点的下一个节点（防止断链） 2.2：将当前节点指向新链表的头部（关键操作：反转指针方向） 2.3：更新新链表的头部为当前节点 2.4：当前节点的位置移动到原链表的下一个节点 第三阶段：返回头节点 3.1：修改原始头指针指向新链表头 3.2：返回反转后的链表头 */
boolchkPalindrome(ListNode* A){structListNode* mid =middleNode(A);structListNode* rmid =reverseList(mid);while(rmid && A){if(rmid->val != A->val)returnfalse; rmid = rmid->next; A = A->next;}returntrue;}/* 第一个阶段：找到链表中的中间节点 第二个阶段：反转后半部分链表 第三个阶段：比较链表的前后两部分是否相等 3.1：使用while循环：链表的后半部分为空时循环结束 3.2：使用if判断：如果当链表的头指针指向的值和链表的中间指针指向的值不相等时，返回false 3.3：移动后半部分反转之后的链表的头指针 3.4：移动前半部分链表的头指针 */
综合：判断链表是否为回文链表
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; */classPalindromeList{public://实现：寻找链表的中间节点： ListNode*middleNode(ListNode* head){//1.定义两个指针，并初始为头节点 ListNode* fast=head; ListNode* slow=head;//2.使用while更新双指针while(fast&&fast->next){ slow=slow->next; fast=fast->next->next;}//3.返回结果return slow;} ListNode*reverseList(ListNode* head){//1.定义三个指针并对其进行初始化 ListNode* next=nullptr; ListNode* newHead=nullptr; ListNode* curr=head;//2.使用一个while循环遍历整个链表while(curr!=nullptr){ next=curr->next; curr->next=newHead; newHead=curr; curr=next;}//3.更新头节点 head=newHead;return head;}boolchkPalindrome(ListNode* A){//时间复杂度O(n)：意味着：我们只能遍历链表一次//空间复杂度O(1)：意味着：我们不能额外的开辟一个数组的空间//1.得到链表的中间节点 ListNode* mid=middleNode(A);//2.得到后半部分反转之后的链表 ListNode* rmid=reverseList(mid);while(rmid){if(A->val!=rmid->val)returnfalse; A=A->next; rmid=rmid->next;}returntrue;}};
题目介绍
方法一：
/** * Definition for singly-linked list. * struct ListNode * { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){//代码逻辑分为两部分：1.判断连个单链表是不是相交链表 2.如果是返回相交的节点//任务1：只需判断两个链表的尾节点的地址是否相等即可（也可以理解为判断两个指针是否相等）//任务2：使用双指针遍历两个链表，何时两个指针的值相等时候，那么指针指向的节点就是开始相交的节点//1. ListNode *tmpA=headA,*tmpB=headB;int lenA=1,lenB=1;while(tmpA->next){ tmpA=tmpA->next; lenA++;}while(tmpB->next){ tmpB=tmpB->next; lenB++;}if(tmpA!=tmpB)returnnullptr;//2.//想要完成任务2我们要保证两个指针是从同一个位置开始进行遍历的//所以：我们应该想让长度长的链表的头指针向后移动到持平//到底哪个链表的长度更长呢？---> 使用假设法int gap=abs(lenA-lenB); ListNode *longList=headA,*shortList=headB;if(lenB>lenA){ longList=headB; shortList=headA;}while(gap--){ longList=longList->next;}while(longList !=nullptr){if(longList==shortList)return longList; longList=longList->next; shortList=shortList->next;}returnnullptr;}};
题目介绍
方法一：
/** * Definition for singly-linked list. * struct ListNode * { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public:boolhasCycle(ListNode *head){//思路：使用快慢指针 ListNode *fast=head,*slow=head;while(fast&&fast->next)//若指针一次可以走两步的话，就是使用这种方式遍历整个链表{ slow=slow->next; fast=fast->next->next;if(fast==slow)returntrue;}returnfalse;}};
思考与探究
题目介绍
方法一：
/** * Definition for singly-linked list. * struct ListNode * { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public: ListNode *detectCycle(ListNode *head){//使用双指针 ListNode *fast=head,*slow=head;//遍历环形链表，并找到快指针和慢指针相遇的地方(若没有相遇，条件会为空，代表链表没有环)while(fast&&fast->next){ slow=slow->next; fast=fast->next->next;if(fast==slow){ ListNode*meet=fast;//遍历环形链表，并使用对撞指针找到链表开始入环的第一个节点while(head!=meet){ head=head->next; meet=meet->next;}return meet;}}returnnullptr;}};
思考与探究
题目介绍
方法一：
/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */classSolution{public: Node*copyRandomList(Node* head){// 对链表进行深拷贝的步骤：// 步骤1：拷贝节点插在原节点的后面// 步骤2：控制random指针// 步骤3：把拷贝节点取下来尾插成新的链表// 1. Node* curr = head;while(curr !=nullptr){//1)创建节点 Node* copy =newNode(curr->val);//2）插入节点 copy->next=curr->next; curr->next=copy;//3）指针移动 curr = copy->next;}// 2.// 情况1：curr指针指向的节点的random指向的null，那么copy指针指向的节点的random指向的也是null// 情况2：curr指针指向的节点的random指向的是某节点，那么copy指针指向的节点的random指向的是：curr->random->next; curr = head;while(curr !=nullptr){//1)创建指针 Node* copy = curr->next;//2）控制random指针if(curr->random ==nullptr) copy->random =nullptr;else copy->random = curr->random->next;//3）指针移动 curr=copy->next;}// 3.// 1）需要使用两个指针遍历两个链表 ---> curr 和 copy// 2）需要使用两个指针：一个保存新链表的头节点、一个处理新链表的next指针// ---> copyhead 和 copytail 3）需要一个指针存储遍历的指针的下一位置 -->// next 因为：在遍历的过程中我们要更改访问到的节点的next指针//0）创建需要根据具体的情况进行更新的指针 + 重置遍历使用的指针 Node *copyhead =nullptr,*copytail =nullptr; curr=head;while(curr !=nullptr){//1）创建每次都要实时更新的指针 Node* copy = curr->next; Node* next = copy->next;//2）核心的剔出新链表的操作（删除操作）if(copyhead==nullptr) copyhead = copytail = copy;else{ copytail->next=copy; copytail=copy;} curr->next=copy->next;//3）移动指针 curr=next;}return copyhead;}};
程序执行流程
题目介绍
方法一：
/** * Definition for singly-linked list. * struct ListNode * { * int val; * struct ListNode *next; * }; */structListNode*removeElements(structListNode* head,int val){//思路1 ---> 本质：在原链表中遍历并将值为val的节点删除掉//1.我们可以再使用一个prev指针去遍历这个链表//2.如果这个prev指针的下一个节点的值等于val的话，就将下一个节点删除掉//0.处理特殊的情况：//情况二：这个链表中有一个或多个节点，并且头节点的值等于val（或者头节点之后连续的出现了多个值为val的节点）while(head!=NULL&&head->val==val){structListNode*del=head; head=head->next;free(del);}//情况一：这个链表中没有节点if(head==NULL)returnNULL;//1.定义一个prev指针指向链表的头指针进行遍历structListNode*prev = head;while(prev->next!=NULL){//2.使用if判断：如果下一个节点是我们要删除的节点 if(prev->next->val==val){//2.1：定义一个指针指向我们要删除的节点structListNode*del=prev->next;//2.2：断开要删除节点的连接 prev->next=prev->next->next;//2.3：释放要删除节点的内存空间free(del);}//这里使用if - else 条件语句原因是：要删除的节点可能是连续的，所以我们不一定每次都要向后移动一次//3.将prev指针往后移动else{ prev=prev->next;}}return head;}
代码片段解释
疑问：为什么要将情况2写在情况1之前，这样你还有多此一举在while循环写一个：head!=NULL&&？
回答：大家提出的这个问题是真的不错啊！！！
但是你心中的这个疑问可以使用下面的这个测试样例来解答
当链表的所有节点都等于 val 时（例如 [6,6,6]，val=6）你的 while (head->val == val) 循环会一直删除头节点，直到 head 变为 NULL但 while (prev->next != NULL) 循环仍然会执行，而 prev 已经是 NULL，导致 访问 prev->next 时出现空指针解引用（Segmentation Fault）
所以：在 while (head->val == val) 循环结束后，必须检查 head 是否为 NULL，如果是，直接返回 NULL，避免后续操作。在while (head->val == val)循环中增加 head != NULL 检查， 确保在 head 变为 NULL 时停止循环。
方法二：
/** * Definition for singly-linked list. * struct ListNode * { * int val; * struct ListNode *next; * }; */structListNode*removeElements(structListNode* head,int val){//思路2 --> 本质：在原链表中遍历并将值不为val的节点尾插到新链表中//1. 我们可以再使用一个pcur指针去遍历这个链表//2.如果pcur指针指向的节点的值不等于val的话，就将该节点尾插到新链表中//1.用于遍历链表 ---> pcur//2.用于记录首元节点的位置 ---> phead//3.用于进行尾插 ---> ptailstructListNode*pcur=head;structListNode*phead=NULL,*ptail=NULL;while(pcur!=NULL){if(pcur->val!=val){//情况1：当链表为空链表时候（第一次插入时候）if(phead==NULL){ phead=ptail=pcur;}//情况2：当链表为非空链表时候 else{ ptail->next=pcur; ptail=ptail->next;}} pcur=pcur->next;}if(ptail!=NULL) ptail->next=NULL;//注意：这里要将尾指针的下一个位置置空//因为：我们本质上并不是创建了一个新的链表，而是在原链表的基础进行了新的连接//当面对测试样例：[1,2,6,3,4,5,6] 6 如果不置空的话，输出会多输出一个6return phead;}
题目介绍
方法一：
/** * Definition for singly-linked list. * struct ListNode * { * int val; * struct ListNode *next; * }; */structListNode*reverseList(structListNode* head){//思路1：本质 ---> 遍历原链表的所有的节点并将其进行头插入到新链表中（本质上并没有创建新的单链表）//1.定义一个pcur指针遍历链表中的所有的节点//2.并将遍历到的每个节点进行头插//1.用于遍历链表 ---> pcur//2.用于记录新链表的首元节点 ---> pheadstructListNode*pcur=head;structListNode*phead=NULL;while(pcur!=NULL){//3.用于记录pcur所指节点的下一个节点structListNode*next=pcur->next; pcur->next=phead; phead=pcur; pcur=next;}return phead;}
题目介绍
方法一：
/** * Definition for singly-linked list. * struct ListNode * { * int val; * struct ListNode *next; * }; */structListNode*middleNode(structListNode* head){//思路：//1.使用遍历同一个链表的快慢指针//2.快指针一次走两步，慢指针一次走一步//3.当快指针到达链表的尾节点时，慢指针正好指向链表的中间节点structListNode*fast=head;structListNode*slow=head;//注意1：fast不为空对应：偶数个节点的结束遍历的情况//注意2：fast->next不为空对应：奇数个节点的结束遍历的情况//注意3：这两个判断条件不能写颠倒while(fast!=NULL&&fast->next!=NULL){ fast=fast->next->next; slow=slow->next;}return slow;}
题目介绍
方法一：
/** * Definition for singly-linked list. * struct ListNode * { * int val; * struct ListNode *next; * }; */structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){//思路：有点类似归并排序最后的操作“两个数组中元素的双路归并”//1.使用两个临时的指针分别遍历两个链表中的所有的节点//2.比较遍历到的两个节点的值的大小//3.值小的节点尾插到新的链表中//两个链表可能出现的所有的情况//1.两个链表中：两个链表都为空//2.两个链表中：一个链表为空，另一个链表不为空//3.两个链表中：两个链表都为不空//处理特殊情况：两个链表都为空if(list1==NULL&&list2==NULL)returnNULL;//处理特殊情况：一个链表为空，另一个链表不为空if(list1==NULL)return list2;if(list2==NULL)return list1;//1.定义两个链表的临时指针遍历两个链表 ---> pcur1 和 pcur2structListNode*pcur1=list1;structListNode*pcur2=list2;//2.用于记录新链表的首元节点的位置 ---> phead//3.用于进行尾插 ----> ptailstructListNode*phead=NULL;structListNode*ptail=NULL;while(pcur1!=NULL&&pcur2!=NULL)//当其中有一个链表遍历结束时整个合并阶段基本上就算是完成任务了 --->两个链表都不为空链表的时候可以进入循环{if(pcur1->val<=pcur2->val){//情况1：空链表的插入 （第一向新链表中进行插入）if(phead==NULL){ phead=ptail=pcur1;}//情况2：非空链表的插入else{ ptail->next=pcur1; ptail=ptail->next;} pcur1=pcur1->next;}else{//情况1：空链表的插入 （第一向新链表中进行插入）if(phead==NULL){ phead=ptail=pcur2;}//情况2：非空链表的插入else{ ptail->next=pcur2; ptail=ptail->next;} pcur2=pcur2->next;}}//当其中一个链表已经遍历完之后，只需要将其中的另一个链表中的剩余的节点尾插到新链表中即可if(pcur1==NULL){ ptail->next=pcur2;}else{ ptail->next=pcur1;}return phead;}
方法二：使用哨兵位进行优化
/** * Definition for singly-linked list. * struct ListNode * { * int val; * struct ListNode *next; * }; */structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){//思路：两个链表进行合并的过程 --> 本质：单链表的尾插 -> 需要考虑被插链表是否为空链表的情况//所以：我们直接将在被插链表中创建一个新的节点“哨兵节点”（保证其一定为非空链表）--> 带头节点的链表//1.使用两个临时的指针分别遍历两个链表中的所有的节点//2.比较遍历到的两个节点的值的大小//3.值小的节点尾插到新的链表中//两个链表可能出现的所有的情况//1.两个链表中：两个链表都为空//2.两个链表中：一个链表为空，另一个链表不为空//3.两个链表中：两个链表都为不空//处理特殊情况：两个链表都为空if(list1==NULL&&list2==NULL)returnNULL;//处理特殊情况：一个链表为空，另一个链表不为空if(list1==NULL)return list2;if(list2==NULL)return list1;//1.定义两个链表的临时指针遍历两个链表 ---> pcur1 和 pcur2structListNode*pcur1=list1;structListNode*pcur2=list2;//2.用于记录新链表的首元节点的位置 ---> phead//3.用于进行尾插 ----> ptailstructListNode*phead=NULL;structListNode*ptail=NULL;//4.创建哨兵节点 phead=ptail=(structListNode*)malloc(sizeof(structListNode));while(pcur1!=NULL&&pcur2!=NULL)//当其中有一个链表遍历结束时整个合并阶段基本上就算是完成任务了 --->两个链表都不为空链表的时候可以进入循环{if(pcur1->val<=pcur2->val){ ptail->next=pcur1; ptail=ptail->next; pcur1=pcur1->next;}else{ ptail->next=pcur2; ptail=ptail->next; pcur2=pcur2->next;}}//当其中一个链表已经遍历完之后，只需要将其中的另一个链表中的剩余的节点尾插到新链表中即可if(pcur1==NULL){ ptail->next=pcur2;}else{ ptail->next=pcur1;}//释放哨兵节点structListNode*next=phead->next;free(phead); phead=next;return phead;}
环形链表的约瑟夫问题
开始挑战： 环形链表的约瑟夫问题
题目介绍
方法一：
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param m int整型 * @return int整型 *///实现：“链表节点的创建”的辅助函数structListNode*CreateNode(int x){structListNode*newNode=(structListNode*)malloc(sizeof(structListNode));if(newNode==NULL){exit(1);} newNode->val=x; newNode->next=NULL;return newNode;}//实现：“将链表的节点连接成环形链表”的辅助函数structListNode*CreateCircle(int n){//1.1：先创建一个首元节点structListNode*phead=CreateNode(1);//1.2：再使用for循环创建出2~n的节点structListNode*ptail=phead;for(int i=2;i<=n;i++){ ptail->next=CreateNode(i); ptail=ptail->next;}//1.3：使创建出来的节点形成环形链表 ptail->next=phead;//2.return ptail;//由于接下来我们要对该环形链表进行删除的操作，//所以这里我们要返回头指针前面的那个指针：尾指针}intysf(int n,int m ){//思路：//1.创建n个节点的单链表，每个节点的值分别设置为1~n//2.遍历单链表，并记录当前的报数//3.当报数的值为m时，删除该节点//1.定义临时指针进行遍历环形链表 --> pcur//2.用于删除下一个节点 ---> prevstructListNode*prev=CreateCircle(n);structListNode*pcur=prev->next;int count=1;//此时while(pcur->next!=pcur)//当环形链表中只剩下一个节点的时候：该节点的下一个节点还是本身{//1.if(count==m){ prev->next=pcur->next;free(pcur); pcur=prev->next; count=1;//重置报数}//2.else{ prev=prev->next; pcur=pcur->next; count++;}}return pcur->val;}
题目介绍
方法一：
/** * Definition for singly-linked list. * struct ListNode * { * int val; * struct ListNode *next; * }; */structListNode*partition(structListNode* head,int x){//思路1：使用一个指针遍历整个链表如果遍历到的节点的值大于等于特定值x的话就将它尾插的原链表//处理特殊的情况：“空链表 + 链表中只有一个节点”if(head ==NULL|| head->next ==NULL){return head;}//0.原链表的尾指针 ---> ptail//1.记录新链表的首元节点 ---> newHead//2.用于尾插 --> newTail//3.用于遍历整个链表 ---> pcur//4.用于删除下一个节点 ---> prevstructListNode*ptail=head;structListNode*newHead=head,*newTail=head;structListNode*pcur=head;structListNode*prev=NULL;while(ptail->next!=NULL){ ptail=ptail->next;} newTail=ptail;while(pcur!=ptail){if(pcur->val>=x){/*--------------第一阶段：将大于或等于特定值x的节点删除掉--------------*/structListNode*next=pcur->next;//但是你要明白在一个链表中将一个节点删除要分类讨论//情况1：要删除的节点是头节点 ---> 相当于头删if(prev==NULL){//1.断 newHead=pcur->next;//2.释//3.移//pcur=pcur->next; 不能立即移动pcur，因为还需要将这个节点尾插到链表尾部}//情况2：要删除的节点不是头节点 ---> 相当于尾删else{//1.断 prev->next=pcur->next;//2.释//3.移//pcur=pcur->next;//prev=prev->next;}/*--------------第二阶段：将断连的节点尾插的原链表的后面--------------*///1.连 newTail->next=pcur;//2.移 newTail=newTail->next; newTail->next =NULL;// 防止成环 pcur=next;//这个时候再移动pcur}else{ prev=pcur; pcur=pcur->next;}}return newHead;}
疑问：上面的代码中为什么需要注释那些代码？关于释放节点（释）：原始代码中注释掉了释放节点的操作，因为：我们不是要真正删除节点，而是将它移动到链表尾部如果调用free(pcur)，节点就被销毁了，无法再使用它进行尾插关于移动指针（移）：原始代码中pcur=pcur->next和prev=prev->next被注释，因为：我们需要先完成当前节点的尾插操作，才能移动指针在第二阶段（尾插部分）统一处理指针移动更安全
方法二：
/** * Definition for singly-linked list. * struct ListNode * { * int val; * struct ListNode *next; * }; */structListNode*partition(structListNode* head,int x){//思路2：将原链表的节点值<特定值x的节点添加到小链表中，否则添加到大链表中，最后将这两个链表首尾相连//处理特殊的情况：“空链表 + 链表中只有一个节点”if(head==NULL||head->next==NULL)return head;/*---------------第一阶段：创建两个带头节点的链表---------------*/structListNode*lessHead,*lessTail;structListNode*greaterHead,*greaterTail; lessHead=lessTail=(structListNode*)malloc(sizeof(structListNode)); lessHead->next=NULL; greaterHead=greaterTail=(structListNode*)malloc(sizeof(structListNode)); greaterHead->next=NULL;/*---------------第二阶段：填充两个带头节点的链表---------------*/structListNode*pcur=head;while(pcur!=NULL){//1.填充小链表 //注意：向一个链表中插入一个节点应该判断：“链表是否为空”，但是我们使用了哨兵节点之后就不需要进行判断了，直接进行插入if(pcur->val<x){ lessTail->next=pcur; lessTail=lessTail->next;}//2.填充大链表else{ greaterTail->next=pcur; greaterTail=greaterTail->next;} pcur=pcur->next;}/*---------------第三阶段：连接两个带头节点的链表---------------*/ lessTail->next=greaterHead->next; greaterTail->next=NULL;//防止成环/*---------------第四阶段：释放哨兵节点---------------*/structListNode*ret=lessHead->next;free(lessHead); lessHead=NULL;free(greaterHead); greaterHead=NULL;return ret;}
