C++单链表相邻节点交换问题：节点丢失排查与修复求助

Let's break down the problems in your code and walk through the fixes step by step:

Key Issues Identified #

1. Root Pointer is Passed by Value
   Your swap function takes root as a value parameter, so any changes you make to root inside the function (like root = B) won't affect the actual root pointer in your LinkedList class. This is why swapping the first two nodes causes a break—your external root still points to the old head node, leaving the new head disconnected from the rest of the list.

2. Redundant and Unnecessary Logic
   Since your sort function only passes adjacent indices (j-1 and j), the indexB == 0 branch will never execute. This is just leftover cruft that can be removed to simplify the code.

3. Minor Sort Loop Inefficiency
   Your outer loop runs i <= getSize(), but bubble sort only needs size - 1 passes (each pass bubbles the largest unsorted element to its correct position, so the last element is already sorted after size-1 iterations).

Fixed Swap Function #

First, update the swap function to use a reference for the root pointer, then simplify the logic for adjacent nodes:

void swap(std::shared_ptr<ListItem>& root, int indexA, int indexB) {
    // Ensure indexA is the left node (since we're only swapping adjacent pairs)
    if (indexA > indexB) {
        std::swap(indexA, indexB);
    }

    if (indexA == 0) {
        // Swap the first two nodes
        std::shared_ptr<ListItem> oldHead = root;
        std::shared_ptr<ListItem> newHead = oldHead->next;
        std::shared_ptr<ListItem> temp = newHead->next;

        newHead->next = oldHead;
        oldHead->next = temp;
        root = newHead; // This change now affects the external root pointer
    } else {
        // Swap two adjacent nodes in the middle/end of the list
        std::shared_ptr<ListItem> preA = GetNode(root, indexA - 1);
        std::shared_ptr<ListItem> nodeA = preA->next;
        std::shared_ptr<ListItem> nodeB = nodeA->next;
        std::shared_ptr<ListItem> temp = nodeB->next;

        preA->next = nodeB;
        nodeB->next = nodeA;
        nodeA->next = temp;
    }
}

Fixed Sort Function #

Adjust the loop condition to avoid unnecessary iterations:

void LinkedList::sort() {
    int listSize = this->getSize();
    // Only need size-1 passes for bubble sort
    for (int i = 0; i < listSize - 1; i++) {
        int j = i;
        while (j > 0 && getItem(j) < getItem(j - 1)) {
            swap(root, j - 1, j);
            j--;
        }
    }
}

Additional Notes #

• Double-check your GetNode function to ensure it correctly returns the node at the given index (starting from 0) without going out of bounds. A bug here would cause unexpected behavior in the swap logic.
• Since you're using std::shared_ptr, you don't have to worry about manual memory leaks, but make sure your link updates don't create unintended cyclic references (the fixed swap logic avoids this).

内容的提问来源于stack exchange，提问作者Alexander Granell