首页 > 代码库 > Partition List leetcode
Partition List leetcode
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2
and x = 3,
return 1->2->2->4->3->5
.
题目意思是根据输入的x值 ,将链表分成两部分,前面的元素为小于x的 后面部分为不小于x的(包括等于x的) 并且各个节点之间次序不变
思路: 遍历链表,当遇到比x小的 插入到当前小于x的最后一个节点,遇到比x大的,继续往后遍历
定义三个指针 p q pur 分别用来表示
p: 当前小于x的最后一个节点
q:往后遍历节点
pur:q之后的一个节点,用来将小于x的节点插入到当前小于x的最后一个节点后面
代码如下:
<span style="font-size:18px;">/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *partition(ListNode *head, int x) { if(head==NULL||head->next==NULL) return head; ListNode *result=new ListNode(0); result->next=head; ListNode *p,*q,*pur;//p用来指向当前小于x的最后一个节点,q用于往后遍历 当找到小于x的节点,放入p后面,pur表示q后的一个元素 p=result; //初始化 q=result; //用来记录第一个 while(q->next) { if(q->next->val<x) { if(p!=q) //表示当前小于x的最后一个节点和 当前遍历节点q中存在其他大于x的点 { pur=q->next->next; q->next->next=p->next; p->next=q->next; q->next=pur; } else //表示当前遍历的所有元素都小于x q=q->next; p=p->next; } else //如果大于x,则继续往后遍历 q=q->next; } return result->next; } };</span>
Partition List leetcode
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。