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.

分析

无

代码

  1. // Partition List
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4.     public ListNode partition(ListNode head, int x) {
  5.         ListNode left_dummy = new ListNode(-1); // 头结点
  6.         ListNode right_dummy = new ListNode(-1); // 头结点
  8.         ListNode left_cur = left_dummy;
  9.         ListNode right_cur = right_dummy;
  11.         for (ListNode cur = head; cur != null; cur = cur.next) {
  12.             if (cur.val < x) {
  13.                 left_cur.next = cur;
  14.                 left_cur = cur;
  15.             } else {
  16.                 right_cur.next = cur;
  17.                 right_cur = cur;
  18.             }
  19.         }
  21.         left_cur.next = right_dummy.next;
  22.         right_cur.next = null;
  24.         return left_dummy.next;
  25.     }
  26. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/linked-list/partition-list.html