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.
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
遍历原链表,用左右子链表,分别对应大于x小于x,最后把两部分连接起来。
public class Solution { //Time: O(n) Space: O(1) public ListNode partition(ListNode head, int x) { if (head == null || head.next == null) { return head; } ListNode dummyleft = new ListNode(0); ListNode dummyright = new ListNode(0); ListNode left = dummyleft; ListNode right = dummyright; while (head != null) { if (head.val < x) { left.next = head; left = left.next; } else { right.next = head; right = right.next; } head = head.next; } left.next = dummyright.next; right.next = null; return dummyleft.next; } }
No comments:
Post a Comment