首页 > 代码库 > 86. Partition List
86. Partition List
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.
使用两个链表newHead1, newHead2，遍历原链表，如果结点值小于x，则挂在newHead1上，如果大于等于x，则挂在newHead2上，最后把newHead2挂在newHead1上。
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode* partition(ListNode* head, int x) {12 ListNode* newHead1 = new ListNode(0);13 ListNode* newHead2 = new ListNode(0);14 15 ListNode* pNode1 = newHead1;16 ListNode* pNode2 = newHead2;17 18 ListNode* pNode = head;19 20 while(pNode){21 if(pNode->val < x){22 pNode1->next = pNode;23 pNode1 = pNode1->next;24 }else{25 pNode2->next = pNode;26 pNode2 = pNode2->next;27 }28 pNode = pNode->next;29 }30 31 pNode2->next = NULL;32 pNode1->next = newHead2->next;33 34 return newHead1->next;35 }36 };
86. Partition List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。