首页 > 代码库 > Partition List
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.
这道题开始没什么思路，后面看到提示说用双指针，有点懂了
思路
找出第一个大于等于x的位置front和前一个位置behind,behind后移，如果behind.val < x在front后面插入值为x的节点
1 public class Solution { 2 public ListNode partition(ListNode head, int x) { 3 ListNode headNode = new ListNode(0); 4 headNode.next = head; 5 6 ListNode front = head; 7 ListNode behind = headNode; //双指针 8 9 while(front != null){ //找出第一个大于等于x的位置和前一个位置10 if(front.val >= x)11 break;12 front = front.next;13 behind = behind.next;14 }//while15 if(front == null)16 return head; //如果原列表符合规定直接返回头结点17 while(front != null &&front.next != null){ //遇到比x小的插入到behind后面，同时删除后面的节点18 if(front.next.val < x){19 ListNode temp = new ListNode(front.next.val);20 temp.next = behind.next;21 behind.next = temp;22 behind = temp;23 front.next = front.next.next; //删除节点24 continue;25 }//if26 front = front.next;27 }//while28 return headNode.next;29 }30 }
这是我在leetcode上面的第100题
Partition List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。