使用指针对链接列表C ++进行排序 [英] Sorting Linked List C++ with pointers

问题描述

我已经为这个问题苦苦挣扎了几个小时.我的目标是仅使用指针对链表进行排序(我无法将链表放入vec或数组中然后进行排序).我得到了指向列表头节点的指针.我只能在指针上调用的方法是head-> next(下一个节点)和head-> key(存储在节点中的int值，用于进行比较).我一直在过度使用白板，并且尝试了所有我能想到的东西.

I have been struggling for hours on end with this problem. My goal is to sort a linked list using only pointers (I cannot place linked list into vec or array and then sort). I am given the pointer to the head node of the list. The only methods i can call on the pointers are head->next (next node) and head->key (value of int stored in node, used to make comparisons). I have been using my whiteboard excessively and have tried just about everything I can think of.

Node* sort_list(Node* head)
{
   Node* tempNode = NULL;
   Node* tempHead = head;
   Node* tempNext = head->next;

   while(tempNext!=NULL) {

       if(tempHead->key > tempNext->key) {
           tempNode = tempHead;
           tempHead = tempNext;
           tempNode->next = tempNode->next->next;
           tempHead->next = tempNode;
           tempNext = tempHead->next;
           print_list(tempHead);


        }
        else {  
            tempHead = tempHead->next;
            tempNext = tempNext->next;

        }
    }
    return head;
}

推荐答案

由于它是单链接列表，因此我们可以执行以下操作:(伪代码)

Since it's a singly linked list, we can do: (psuedo code)

bool unsorted = true;
while(unsorted) {
    unsorted = false;
    cur = head;         

    while(cur != nullptr) {
        next = cur->next;
        if(next < cur) {
            swap(cur, next)
            unsorted = true;
        }

        cur = cur->next;
    }       
}

这篇关于使用指针对链接列表C ++进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！