首页 > 代码库 > Leetcode-Partition List
Leetcode-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.
Analysis:
The first element that is not less than x is the point of partition. We record this node and its predecessor. Once we encount a node that is less than x later, we insert it between the point and its predecessor, then update the predecssor to this node.
Solution:
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * }10 * }11 */12 public class Solution {13 public ListNode partition(ListNode head, int x) {14 if (head==null || head.next==null) return head;15 ListNode preHead = new ListNode(-1);16 preHead.next = head;17 ListNode preStart = null,start=null;18 ListNode cur = head;19 ListNode pre = preHead;20 21 while (cur.val<x && cur.next!=null){22 pre = cur;23 cur = cur.next;24 }25 26 if (cur.next==null) return head;27 28 start = cur;29 preStart = pre;30 pre = cur;31 cur = cur.next;32 while (cur!=null){33 if (cur.val<x){34 pre.next = cur.next;35 preStart.next = cur;36 cur.next = start;37 preStart = cur;38 cur = pre.next;39 } else {40 pre = cur;41 cur = cur.next;42 }43 }44 45 return preHead.next; 46 }47 }
Leetcode-Partition List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。