为什么我无法让基于指针的链表气泡交换工作？

Question

class Node {
    
    
public:
    int data;
    Node* next;

    Node() { //default constructor
        data = NULL;
        next = NULL;
    }

    Node(int value) {
        this->data = value;
        this->next = NULL;
    }
};

class linkedList {
    Node* head;

public:
    linkedList() {
        head = NULL;
    }

    void insertVal(int val)
    {
        Node* newNode = new Node(val);
        if (head == NULL)
        {
            head = newNode;
            return;
        }
        Node* temp = head; //iterator
        while (temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = newNode;

    }

    void deleteAtIndex(int index)
    {
        int listLen = 1;
        if (head == NULL)
        {
            std::cout << "cannot delete from null list\n";
            return;
        }

        Node* temp = head;
        while (temp != NULL)
        {
            temp = temp->next;
            listLen++;
        }
        
        if (index > listLen)
        {
            std::cout << "deletion index out of bounds\n";
        }

        temp = head;
        if (index == 1)
        {
            head = head->next;
            delete temp;
            return;
        }

        Node* temp2 = NULL;

        while (index-- > 1)
        {
            temp2 = temp;
            temp = temp->next;
        }
        temp2->next = temp->next;
        delete temp;
    }

    void print() {
        Node* temp = head;

        if (temp == NULL)
        {
            std::cout << "no printo from listo emptyo\n";
            return;
        }
        while(temp != NULL)
        {
            std::cout << temp->data << std::endl;
            temp = temp->next;
        }
    }

    void bubbleSort()
    {
        if (!head || !head->next) // checks if list is empty or singleton
        {
            std::cout << "already sorted\n";
            return;
        }

        bool swapped; // checks if a pass occured with no swaps

        Node* current;
        Node* lastSorted = NULL;

        do {
            swapped = false;
            current = head;

            while (current->next != lastSorted)
            {
                if (current->data > current->next->data)
                {
                    Node* temp = current->next;
                    temp->next = current;
                    temp->next->next = current->next->next; // AAAAAARRRRRRRRRRRRRRRRRGHHHHHHHHHHHHHHH!!!!!!!

                    
                    current = temp;
                }
                current = current->next;
            }
        } while (swapped);
    }
};

我已经设置了基于链表节点，但是当我去打印交换列表时，我觉得我的交换算法只是删除整个列表？它根本不会打印任何内容，甚至不会打印已经排序的列表的初始元素。

我尝试重写算法四次，但我完全迷失了。我的教授说，对于我们的编程测试，我们必须进行基于指针的交换工作，但我们的助教给出的示例是基于值的交换。

Answer 1

考虑交换时当前指针如何变化。我建议您使用两个临时指针 tempA 和 tempB 可能会更好。

指针可能很棘手。画一些链接的图片，因为它们随着每行代码的变化而变化。

这里有一个建议：考虑一下你的删除方法。如何将一个项目插入到列表中紧邻列表中给定项目指针之后？您可以通过删除当前项目并将其插回较小项目之后来进行交换。

希望有帮助， 埃德

Minor：lastsorted 永远不会更新，因此它的作用类似于 null 的别名。当您的意思是 null 时，请使用 null。