首页 > 代码库 > leetcode 链表 Partition List
leetcode 链表 Partition List
Partition List
Total Accepted: 19761 Total Submissions: 73252My SubmissionsGiven 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小的节点的链表l1，另一个是大于等于x的节点的链表l2
最后把l1的尾部接到l2的头部
复杂度：时间O(n)，空间O(1)
ListNode *partition(ListNode *head, int x) {
ListNode less(-1), larger_equal(-1);
ListNode *less_ptr = &less, *larger_equal_ptr = &larger_equal;
for (ListNode *cur = head; cur != NULL; cur = cur->next)
{
if(cur->val < x){
less_ptr = less_ptr->next = cur;
}else{
larger_equal_ptr = larger_equal_ptr->next = cur;
}
}
less_ptr->next = larger_equal.next;
larger_equal_ptr->next = NULL;
return less.next;
}leetcode 链表 Partition List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。