Sortierung verkettete Liste C++ mit Zeigern

Fühle mich nicht schlecht, das ist viel schwieriger, als es klingt. Wenn dies in einem array wäre es deutlich einfacher. Wenn die Liste waren doppelt verkettete wäre es einfacher. Werfen Sie einen Blick auf diesen code, setzt eine insertion sort

struct Node {
    int key;
    Node *next;
    } *NodePtr;

//do a simple selection sort http://en.wikipedia.org/wiki/Selection_sort
Node* sort_list(Node* head) {
    Node *top = nullptr; //first Node we will return this value
    Node *current = nullptr;
    bool sorted = false;
    while (sorted == false) {
        //we are going to look for the lowest value in the list
        Node *parent = head;
        Node *lowparent = head; //we need this because list is only linked forward
        Node *low = head; //this will end up with the lowest Node
        sorted = true;
        do {
            //find the lowest valued key
            Node* next = parent->next;
            if (parent->key > next->key) {
                lowparent = parent;
                low = next;
                sorted = false;
                }
            parent = parent->next;
            } while (parent->next != nullptr);
        if (current != nullptr) { //first time current == nullptr
            current->next = low;
            }
        //remove the lowest item from the list and reconnect the list
        //basically you are forming two lists, one with the sorted Nodes 
        //and one with the remaining unsorted Nodes
        current = low;
        if (current == head) { head = current->next; }
        lowparent->next = low->next;
        current->next = nullptr;
        if (top == nullptr) {
            top = current;
            }
        };
    current->next = head;
    return top;
    }

int _tmain(int argc, _TCHAR* argv []) {
    Node nodes[4];
    nodes[0].key = 3;
    nodes[1].key = 4;
    nodes[2].key = 5;
    nodes[3].key = 1;

    nodes[0].next = &nodes[1];
    nodes[1].next = &nodes[2];
    nodes[2].next = &nodes[3];
    nodes[3].next = nullptr;

    auto sortedNodes = sort_list(&nodes[0]);

    return 0;
    }

Übernehmen die Knoten wie dieser:

struct Node
{
    Node *next;
    int key;
    Node(int x) : key(x), next(NULL) {}
};

Verwendung der insertion-sort-Algorithmus zum Sortieren der Liste:

Node* sort_list(Node* head)
{
    Node dumy_node(0);
    Node *cur_node = head;

    while (cur_node)
    {
        Node *insert_cur_pos =  dumy_node.next;
        Node *insert_pre_pos = NULL;

        while (insert_cur_pos)
        {
            if (insert_cur_pos->key > cur_node->key)
                break;

            insert_pre_pos = insert_cur_pos;
            insert_cur_pos = insert_cur_pos->next;
        }

        if (!insert_pre_pos)
            insert_pre_pos = &dumy_node;

        Node *temp_node = cur_node->next;

        cur_node->next = insert_pre_pos->next;
        insert_pre_pos->next = cur_node;

        cur_node = temp_node;
    }

    return dumy_node.next;
}

Hier ist meine Merge-sort Durchführung mit O(N*logN) Zeit, die Komplexität und die ständigen zusätzlichen Raum. Verwendet C++11

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

typedef pair<ListNode*, ListNode*> PP;

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head==nullptr)return head;
        if (head->next==nullptr) return head;
        if (head->next->next==nullptr){
            if (head->val<=head->next->val){
                return head;
            }
            else {
                ListNode* second=head->next;
                second->next=head;
                head->next=nullptr;
                return second;
            }
        }else {
            PP splitted=split(head);
            return merge(sortList(splitted.first),sortList(splitted.second));
        }
    }

private:  

    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode * head=new ListNode(0);
        ListNode * current=head;
        if (l1==nullptr)return l2;
        if (l2==nullptr)return l1;
        do {
            if (l1->val<=l2->val){
                current->next=l1;
                l1=l1->next;
            }else{
                current->next=l2;
                l2=l2->next;
            }
            current=current->next;
        }while (l1!=nullptr && l2!=nullptr);
        if (l1==nullptr)current->next=l2;
        else current->next=l1;
        return head->next;
    }

    PP split(ListNode* node){
        ListNode* slow=node;
        ListNode* fast=node;
        ListNode* prev;
        while(fast!=nullptr){
            if (fast->next!=nullptr){
                prev=slow;
                slow=slow->next;
                fast=fast->next;
            }else break;
            if(fast->next!=nullptr){
                    fast=fast->next;
                }
            else break;            
        }
        prev->next=nullptr;
        return {node,slow};
    }

};