题目概要

将链表中小于某个值的结点移到链表最前方。

原题链接

Partition List

题目解析

简单的数据结构题，解题思路如下：

1. 迭代链表，将之分为两部分，一条小于x，一条不小于x
2. 合并两条链表

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
    ListNode* nextNode(ListNode*& head) {
        if (head == NULL)
            return NULL;
        ListNode* current = head;
        head = head->next;
        current->next = NULL;
        return current;
    }
    
    void pushBack(ListNode*& head, ListNode*& tail, ListNode* node) {
        if (head == NULL || tail == NULL) {
            head = tail = node;
            return;
        }
        tail->next = node;
        tail = node;
        return;
    }
    
public:
    ListNode* partition(ListNode* head, int x) {
        if (head == NULL || head->next == NULL)
            return head;
        
        ListNode* less = NULL;
        ListNode* lessTail = NULL;
        ListNode* notLess = NULL;
        ListNode* notLessTail = NULL;
        ListNode* current = NULL;
        
        while(head != NULL) {
            current = nextNode(head);
            if (current->val < x) {
                pushBack(less, lessTail, current);
            }
            else {
                pushBack(notLess, notLessTail, current);
            }
        }
        
        if (less == NULL)
            return notLess;
        
        if (lessTail != NULL)
            lessTail->next = notLess;
        return less;
    }
};

广告区域

本人和小伙伴们承接各种软件项目，有需求的可以联系我们。
QQ: 2992073083