什么会导致循环链表

Question

我正在尝试为单链表制作一个快速排序算法。然而，我一定是在这个过程中以某种方式创建了一个循环列表。在 concatenate 函数中，while 循环卡住连续打印出 2 和 22。因此，我假设我必须以某种方式创建一个列表，其中节点 2 指向节点 22，反之亦然。不幸的是，我不知道该怎么做，因为我觉得我已经在每个重要的列表末尾添加了nullptr。我已经检查了我的 partition 函数很多次，我添加的错误比我修复的还要多。链表的工作方式有什么我遗漏的吗？ 我已经坚持了一段时间所以任何帮助将不胜感激。

这是我的快速排序代码。

// quick.cpp

#include "volsort.h"

#include <iostream>
#include <string>

using namespace std;

// Prototypes

Node *qsort(Node *head, bool numeric);
void  partition(Node *head, Node *pivot, Node *&left, Node *&right, bool numeric);
Node *concatenate(Node *left, Node *right);

// Implementations

void quick_sort(List &l, bool numeric) {
    l.head = qsort(l.head, numeric);
}

Node *qsort(Node *head, bool numeric) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    Node *l = nullptr;
    Node *r = nullptr;
    partition(head, head, l, r, numeric);
    l = qsort(l, numeric);
    r = qsort(r, numeric);
    head = concatenate(l, head);
    head = concatenate(head, r);
    return head;
}


void partition(Node *head, Node *pivot, Node *&left, Node *&right, bool numeric) {
    Node *cur = pivot->next;
    bool c;
    Node *tl=nullptr, *tr=nullptr;

    while (cur != pivot && cur != nullptr) {
        if (numeric) { 
            c = node_number_compare(cur, pivot);//compare numeric elements of the Nodes
        }
        else { 
            c = node_string_compare(cur, pivot);//compare string elements of the code
        }
        if (c) {
            if (left == nullptr) {
                left = cur;
                cur = cur->next;
                tl = left;
            }
            else {
                tl->next = cur;
                cur = cur->next;
                tl = tl->next;
                tl->next = nullptr;
            }
        }
        else {
            if (right == nullptr) {
                right = cur;
                cur = cur->next;
                tr = right;
            }
            else {
                tr->next = cur;
                cur = cur->next;
                tr = tr->next;
                tr->next = nullptr;
            }
        } 
    } 
} 

Node *concatenate(Node *left, Node *right) {
    if (right == nullptr && left == nullptr) {
        return nullptr;
    }
    else if (left == nullptr) {
        right->next = nullptr;
        return right;
    }
    else if (right == nullptr) {
        left->next = nullptr;
        return left;
    } 
    
    Node *t = left;
    while (t->next != nullptr) {
        cout << t->number << endl;
        t = t->next;
    }

    t->next = right;
    while (t->next != nullptr) {
        cout << t->number << endl;
        t = t->next;
    }
    t->next = nullptr;
    return left;
} 

输入：

45
4
9
22
2

如果有帮助，这里是列表类函数。

#include "volsort.h"
#include <string>
#include <iostream>

List::List() {
  head = NULL;
  size = 0;
}

List::~List() {
  if (head != NULL) { // follow the links, destroying as we go
    Node *p = head;

  while (p != NULL) {
      Node *next = p->next; // retrieve this node's "next" before destroy it
      delete p;
      p = next;
  }
  }
}

bool node_number_compare(const Node *a, const Node *b) {
  if (a->number <= b-> number) {
    return true;
  }
  else {
    return false;
  }
}

bool node_string_compare(const Node *a, const Node *b) {
  return a->string <= b->string;
}

void List::push_front(const std::string &s) {
  Node *node = new Node();
  node->next = NULL;
  node->string = s;
  node->number = std::stoi(s);
  if (head == NULL) {
    head = node;
    size = 1;
  }
  else {
  Node *p = head;
  while (p->next != NULL) {p = p->next;} // go to end of list
  p->next = node;
  size++;
  }
}

void List::dump_node(Node *n) {
  while (n->next != NULL) {
    std::cout << n->number << " " << n->string << std::endl;
  }
}