做vr网站,0基础如何做网站,手机网站建设报价,建湖人才网招工86.分隔链表
因为对链表中的一个节点进行更换位置的操作需要知道该节点的上一个节点 所以建立一个虚拟头节点
ListNode* pnew ListNode(-201,head);根据题意#xff0c;我们需要找到第一个大于x或等于x的节点large 并且将第一个大于或等于x的节点large后的所有小于x的节点都…86.分隔链表
因为对链表中的一个节点进行更换位置的操作需要知道该节点的上一个节点 所以建立一个虚拟头节点
ListNode* pnew ListNode(-201,head);根据题意我们需要找到第一个大于x或等于x的节点large 并且将第一个大于或等于x的节点large后的所有小于x的节点都挪到large前 但是在代码里为了方便挪动节点位置large为第一个大于x的节点的前一个节点 首先我们要找到第一个大于或等于x的节点
ListNode* pnew ListNode(-201,head);
ListNode* largep;
ListNode* curp;
int flag0;
while(cur-next)
{if(cur-next-valxflag0){largecur;flag1;}curcur-next;
}然后再从large后第一个节点开始找找那些小于x的节点并挪到large前 这一步要分三个情况
当前节点cur大于等于xcur指向下一个节点当前节点cur小于x且当前节点不是链表最后一个节点正常挪当前节点cur小于x且当前节点是链表最后一个节点这个时候指针变换时有一个会指向nullptr要特别写出来
curlarge-next;
while(curcur-next)
{if(cur-next-valxcur-next-next){ListNode* temp1large-next;ListNode* temp2cur-next-next;large-nextcur-next;cur-next-nexttemp1;cur-nexttemp2;largelarge-next;}else if(cur-next-valxcur-next-nextnullptr){ListNode* temp1large-next;large-nextcur-next;cur-next-nexttemp1;cur-nextnullptr;largelarge-next;}elsecurcur-next;
}
return p-next;最后增加一些边界条件
if(headnullptr||head-nextnullptr)return head;
if(flag0)//如果找不到大于x的节点
{return p-next;
}整合起来
/*** 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) {}* };*/
class Solution {
public:ListNode* partition(ListNode* head, int x) {ListNode* pnew ListNode(-201,head);ListNode* largep;ListNode* curp;int flag0;if(headnullptr||head-nextnullptr)return head;while(cur-next){if(cur-next-valxflag0){largecur;flag1;}curcur-next;}if(flag0)//如果找不到大于x的节点{return p-next;}curlarge-next;while(curcur-next){if(cur-next-valxcur-next-next){ListNode* temp1large-next;ListNode* temp2cur-next-next;large-nextcur-next;cur-next-nexttemp1;cur-nexttemp2;largelarge-next;}else if(cur-next-valxcur-next-nextnullptr){ListNode* temp1large-next;large-nextcur-next;cur-next-nexttemp1;cur-nextnullptr;largelarge-next;}elsecurcur-next;}return p-next;}
};不过 其实第二步从large后开始找小于x的数完全可以合到第一步的循环里做 这部分需要再优化一下
