问题描述：

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.

原问题链接：https://leetcode.com/problems/partition-list/

?

问题分析

　　这个问题的思路其实比较简单，我们需要将一个链表按照某个给定的值给划分成两个部分。一个部分小于这个值，一个部分大于这个值。那么我们可以声明两个链表节点，一个保存小于这个值的元素，另外一个保存大于或者等于这个值的元素。

　　我们需要遍历这个链表，每次碰到小于值的元素，则将它放到小于这个元素的链表里，否则放入另外一个链表里。所以需要额外定义两个元素来专门跟踪这两个链表的尾部。在遍历完之后还需要将大的那个链表的最后一个元素的next设置为null。

　　详细的代码实现如下：

?

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head == null || head.next == null) return head;
        ListNode lessNode = new ListNode(0), biggerNode = new ListNode(0);
        ListNode lessHead = lessNode, biggerHead = biggerNode, cur = head;
        while(cur != null) {
            if(cur.val < x) {
              lessHead.next = cur;
              lessHead = lessHead.next;
            } else {
                biggerHead.next = cur;
                biggerHead = biggerHead.next;
            }
            cur = cur.next;
        }
        biggerHead.next = null;
        lessHead.next = biggerNode.next;
        return lessNode.next;
    }
}

　　这里的代码实现并不复杂，只是很容易出错。很多细节需要注意。

?

leetcode: Partition List

原文：http://shmilyaw-hotmail-com.iteye.com/blog/2304309