Linked List - Partition List

by LauCyun Sep 19,2014 14:57:44 3,696 views

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节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Create a new list node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *
newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * 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.
 *
 * For example
 *   Given 1->4->3->2->5->2 and x = 3,
 *   return 1->2->2->4->3->5.
 *
 * @param head: The linked list of headers.
 * @param x: a value x.
 * @return: The linked list of headers.
 */
struct ListNode *
partition(struct ListNode *head, const int x) {
    if (head == NULL) {
        return NULL;
    }

    struct ListNode *leftDummy = newNode(-1);
    struct ListNode *left = leftDummy;
    struct ListNode *rightDummy = newNode(-1);
    struct ListNode *right = rightDummy;
    struct ListNode *curr = head;
    while (curr != NULL) {
        if (curr->val < x) {
            left->next = curr;
            left = left->next;
        } else {
            right->next = curr;
            right = right->next;
        }
        curr = curr->next;
    }

    // post-processing
    right->next = NULL;
    left->next = rightDummy->next;
    free(rightDummy);

    head = leftDummy->next;
    free(leftDummy);
    return head;
}

源码分析

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

其主要过程如下图:

复杂度分析

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

Tags