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).