題目概要

將鏈表中小于某個值的結點移到鏈表最前方。

原題鏈接

Partition List

題目解析

簡單的數(shù)據結構題，解題思路如下：

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;
    }
};

廣告區(qū)域

本人和小伙伴們承接各種軟件項目，有需求的可以聯(lián)系我們。
QQ: 2992073083