Partition List · 數據結構與算法/leetcode/lintcode題解

# Partition List ### Source - leetcode: [Partition List | LeetCode OJ](https://leetcode.com/problems/partition-list/) - lintcode: [(96) Partition List](http://www.lintcode.com/en/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->null and x = 3, return 1->2->2->4->3->5->null. ~~~ ### 題解此題出自 *CTCI* 題 2.4，依據題意，是要根據值x對鏈表進行分割操作，具體是指將所有小于x的節點放到不小于x的節點之前，咋一看和快速排序的分割有些類似，但是這個題的不同之處在于只要求將小于x的節點放到前面，而并不要求對元素進行排序。這種分割的題使用兩路指針即可輕松解決。左邊指針指向小于x的節點，右邊指針指向不小于x的節點。由于左右頭節點不確定，我們可以使用兩個dummy節點。 ### Python ~~~ """ Definition of ListNode class ListNode(object): def __init__(self, val, next=None): self.val = val self.next = next """ class Solution: """ @param head: The first node of linked list. @param x: an integer @return: a ListNode """ def partition(self, head, x): if head is None: return None leftDummy = ListNode(0) left = leftDummy rightDummy = ListNode(0) right = rightDummy node = head while node is not None: if node.val < x: left.next = node left = left.next else: right.next = node right = right.next node = node.next # post-processing right.next = None left.next = rightDummy.next return leftDummy.next ~~~ ### C++ ~~~ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* partition(ListNode* head, int x) { if (head == NULL) return NULL; ListNode *leftDummy = new ListNode(0); ListNode *left = leftDummy; ListNode *rightDummy = new ListNode(0); ListNode *right = rightDummy; ListNode *node = head; while (node != NULL) { if (node->val < x) { left->next = node; left = left->next; } else { right->next = node; right = right->next; } node = node->next; } // post-processing right->next = NULL; left->next = rightDummy->next; return leftDummy->next; } }; ~~~ ### 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) { if (head == null) return null; ListNode leftDummy = new ListNode(0); ListNode left = leftDummy; ListNode rightDummy = new ListNode(0); ListNode right = rightDummy; ListNode node = head; while (node != null) { if (node.val < x) { left.next = node; left = left.next; } else { right.next = node; right = right.next; } node = node.next; } // post-processing right.next = null; left.next = rightDummy.next; return leftDummy.next; } } ~~~ ### 源碼分析 1. 異常處理 1. 引入左右兩個dummy節點及left和right左右尾指針 1. 遍歷原鏈表 1. 處理右鏈表，置`right->next`為空，將右鏈表的頭部鏈接到左鏈表尾指針的next，返回左鏈表的頭部 ### 復雜度分析遍歷鏈表一次，時間復雜度近似為 O(n)O(n)O(n), 使用了兩個 dummy 節點及中間變量，空間復雜度近似為 O(1)O(1)O(1).