Partition List

Question

Problem Statement

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.

题解

此题出自 CTCI 题 2.4，依据题意，是要根据值x对链表进行分割操作，具体是指将所有小于x的节点放到不小于x的节点之前，咋一看和快速排序的分割有些类似，但是这个题的不同之处在于只要求将小于x的节点放到前面，而并不要求对元素进行排序。

这种分割的题使用两路指针即可轻松解决。左边指针指向小于x的节点，右边指针指向不小于x的节点。由于左右头节点不确定，我们可以使用两个dummy节点。

Python

  1. """
  2. Definition of ListNode
  3. class ListNode(object):
  5.     def __init__(self, val, next=None):
  6.         self.val = val
  7.         self.next = next
  8. """
  9. class Solution:
  10.     """
  11.     @param head: The first node of linked list.
  12.     @param x: an integer
  13.     @return: a ListNode
  14.     """
  15.     def partition(self, head, x):
  16.         if head is None:
  17.             return None
  19.         leftDummy = ListNode(0)
  20.         left = leftDummy
  21.         rightDummy = ListNode(0)
  22.         right = rightDummy
  23.         node = head
  24.         while node is not None:
  25.             if node.val < x:
  26.                 left.next = node
  27.                 left = left.next
  28.             else:
  29.                 right.next = node
  30.                 right = right.next
  31.             node = node.next
  32.         # post-processing
  33.         right.next = None
  34.         left.next = rightDummy.next
  36.         return leftDummy.next

C++

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* partition(ListNode* head, int x) {
  12.         if (head == NULL) return NULL;
  14.         ListNode *leftDummy = new ListNode(0);
  15.         ListNode *left = leftDummy;
  16.         ListNode *rightDummy = new ListNode(0);
  17.         ListNode *right = rightDummy;
  18.         ListNode *node = head;
  19.         while (node != NULL) {
  20.             if (node->val < x) {
  21.                 left->next = node;
  22.                 left = left->next;
  23.             } else {
  24.                 right->next = node;
  25.                 right = right->next;
  26.             }
  27.             node = node->next;
  28.         }
  29.         // post-processing
  30.         right->next = NULL;
  31.         left->next = rightDummy->next;
  33.         return leftDummy->next;
  34.     }
  35. };

Java

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. public class Solution {
  10.     public ListNode partition(ListNode head, int x) {
  11.         ListNode leftDummy = new ListNode(0);
  12.         ListNode leftCurr = leftDummy;
  13.         ListNode rightDummy = new ListNode(0);
  14.         ListNode rightCurr = rightDummy;
  16.         ListNode runner = head;
  17.         while (runner != null) {
  18.             if (runner.val < x) {
  19.                 leftCurr.next = runner;
  20.                 leftCurr = leftCurr.next;
  21.             } else {
  22.                 rightCurr.next = runner;
  23.                 rightCurr = rightCurr.next;
  24.             }
  25.             runner = runner.next;
  26.         }
  28.         // cut off ListNode after rightCurr to avoid cylic
  29.         rightCurr.next = null;
  30.         leftCurr.next = rightDummy.next;
  32.         return leftDummy.next;
  33.     }
  34. }

源码分析

  1. 异常处理
  2. 引入左右两个dummy节点及left和right左右尾指针
  3. 遍历原链表
  4. 处理右链表，置right->next为空(否则如果不为尾节点则会报错，处理链表时 以 null 为判断)，将右链表的头部链接到左链表尾指针的next，返回左链表的头部

复杂度分析

遍历链表一次，时间复杂度近似为 O(n), 使用了两个 dummy 节点及中间变量，空间复杂度近似为 O(1).