86.Partition-List

86. Partition List

题目地址

https://www.lintcode.com/problem/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.

代码

public class Solution {
    public ListNode partition(ListNode node, int x) {
    ListNode leftDummy = new ListNode(0);
    ListNode leftCurr = leftDummy;
    ListNode rightDummy = new ListNode(9);
    ListNode rightCurr = rightDummy;

    ListNode runner = node;
    while (runner != null) {
      if (runner.val < x) {
        leftCurr.next = runner;
        letCurr = leftCurr.next;
      } else {
        rightCurr.next = runner;
        rithCurr = rightCurr.next;
      }
      runner = runner.next;
    }

    rightCurr.next = null;
    leftCurr.next = rightDummy.next;

    return leftDummy.next;
  }
}