链表划分

LRH1993 · LRH1993 · commit aa780bb002e9 · 2017-10-14T10:01:16.000+08:00
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -205,6 +205,7 @@
     - [Length of Last Word](/algorithm/LeetCode/String/Length-of-Last-Word.md)
   - [Linked List](/algorithm/LeetCode/Linked-List.md)
     - [Remove Duplicates from Sorted List](/algorithm/LeetCode/Linked-List/Remove-Duplicates-from-Sorted-List.md)
+    - [Partition List](/algorithm/LeetCode/Linked-List/Partition-List.md)
 
 ## 设计模式
 
diff --git a/algorithm/LeetCode/Linked-List/Partition-List.md b/algorithm/LeetCode/Linked-List/Partition-List.md
@@ -0,0 +1,59 @@
+## 一、题目
+
+> 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`.
+
+给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。
+
+你应该保留两部分内链表节点原有的相对顺序。
+
+## 二、解题思路
+
+依据题意，是要根据值x对链表进行分割操作，具体是指将所有小于x的节点放到不小于x的节点之前，咋一看和快速排序的分割有些类似，但是这个题的不同之处在于只要求将小于x的节点放到前面，而并不要求对元素进行排序。
+
+这种分割的题使用两路指针即可轻松解决。左边指针指向小于x的节点，右边指针指向不小于x的节点。由于左右头节点不确定，我们可以使用两个dummy节点。
+
+## 三、解题代码
+
+```java
+/**
+ * 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) {
+        ListNode leftDummy = new ListNode(0);
+        ListNode leftCurr = leftDummy;
+        ListNode rightDummy = new ListNode(0);
+        ListNode rightCurr = rightDummy;
+
+        ListNode runner = head;
+        while (runner != null) {
+            if (runner.val < x) {
+                leftCurr.next = runner;
+                leftCurr = leftCurr.next;
+            } else {
+                rightCurr.next = runner;
+                rightCurr = rightCurr.next;
+            }
+            runner = runner.next;
+        }
+
+        // cut off ListNode after rightCurr to avoid cylic
+        rightCurr.next = null;
+        leftCurr.next = rightDummy.next;
+
+        return leftDummy.next;
+    }
+}
+```
+
