c++单链表和双链表

<think>嗯，用户想用C或C++实现单链表或双链表的逆序输出。我得先回想一下链表的基本结构。单链表每个节点包含数据和指向下一个节点的指针，而双链表则还有指向前一个节点的指针。逆序输出的话，通常有两种方法：一种是直接反转链表结构，另一种是用栈或者递归来反向访问节点。 首先，对于单链表，直接反转结构的话，需要改变指针的方向。记得三个指针，prev、current和next，逐个节点反转。反转完成后，原来的头节点变成尾节点，然后依次遍历输出即可。不过要注意，这样做会改变原链表的结构，如果用户不希望改变原链表，可能需要先复制一份或者使用其他方法。 另一种方法是用栈，遍历链表时将每个节点压入栈，然后依次弹出并输出，这样就能实现逆序。或者用递归，递归到链表末尾，然后逐层返回时输出节点数据。但递归可能在链表很长时导致栈溢出，需要考虑这种情况。 对于双链表，由于有前驱指针，逆序输出应该更简单。可以直接从尾节点开始，向前遍历输出。但如果是反转结构的话，同样需要调整两个指针，不过可能比单链表容易一些，因为可以直接访问前驱节点。 接下来，我需要考虑用户可能的代码示例。比如单链表的结构定义，反转函数的实现，以及如何输出。要注意指针操作的正确性，避免内存泄漏或者空指针访问。比如在反转单链表时，初始prev设为nullptr，current指向头节点，然后循环处理每个节点，将current的next指向prev，然后prev和current依次后移。 对于双链表的反转，可能需要交换每个节点的next和prev指针，然后调整头尾指针的位置。不过如果只是逆序输出而不修改结构，直接遍历到尾节点，然后向前遍历即可。 另外，用户可能关心时间和空间复杂度。反转单链表的时间是O(n)，空间O(1)。栈的方法则是时间O(n)，空间O(n)。递归同样空间O(n)。双链表的情况类似，但直接反向遍历的时间O(n)，空间O(1)。 需要注意代码示例的正确性，比如指针操作是否正确，边界条件处理，比如空链表或者只有一个节点的情况。还有在C++中，使用nullptr而不是NULL，以及可能的头节点处理问题。 最后，用户可能想知道如何选择方法。如果允许修改原链表，反转结构更节省空间。否则，使用栈或递归，但需要考虑空间开销。对于双链表，直接反向遍历是最优解，不需要额外空间或修改结构。</think>### C/C++实现链表逆序输出的方法 #### 一、单链表逆序输出 **方法1：反转链表后顺序输出**（修改原链表结构） ```cpp struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode *prev = nullptr, *curr = head; while (curr) { ListNode* nextTemp = curr->next; curr->next = prev; prev = curr; curr = nextTemp; } return prev; } void printReversed(ListNode* head) { ListNode* reversedHead = reverseList(head); while (reversedHead) { cout << reversedHead->val << " "; reversedHead = reversedHead->next; } } ``` **时间复杂度**：$O(n)$，**空间复杂度**：$O(1)$[^4] **方法2：使用栈辅助输出**（不修改原链表） ```cpp void printReversedWithoutModify(ListNode* head) { stack<int> st; while (head) { st.push(head->val); head = head->next; } while (!st.empty()) { cout << st.top() << " "; st.pop(); } } ``` **时间复杂度**：$O(n)$，**空间复杂度**：$O(n)$ --- #### 二、双链表逆序输出 **利用前驱指针直接反向遍历** ```cpp struct DListNode { int val; DListNode *prev, *next; DListNode(int x) : val(x), prev(nullptr), next(nullptr) {} }; void printReversedDList(DListNode* head) { // 先找到尾节点 DListNode* tail = head; while (tail && tail->next) tail = tail->next; // 反向遍历 while (tail) { cout << tail->val << " "; tail = tail->prev; } } ``` **时间复杂度**：$O(n)$，**空间复杂度**：$O(1)$[^2] --- #### 三、关键点对比 | 方法 | 适用类型 | 是否修改原结构 | 空间复杂度 | |--------------------|----------|----------------|------------| | 链表反转 | 单链表 | 是 | $O(1)$ | | 栈辅助 | 单链表 | 否 | $O(n)$ | | 直接反向遍历 | 双链表 | 否 | $O(1)$ | ---

在C++中，我们可以分别为单链表和双向链表编写交换相邻两个节点的函数。这里提供简单的示例： **对于单链表：** ```cpp #include <iostream> struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; void swapAdjacentNodes(ListNode*& head) { if (head == nullptr || head->next == nullptr) return; ListNode temp = *head; ListNode* nextTemp = head->next; head->next = nextTemp->next; nextTemp->next = temp; temp.next = nullptr; // 如果原头结点是新链表的第一个，需要置空 if (head->next != nullptr) head->next->prev = head; } // 示例如何使用 int main() { ListNode* list = new ListNode(1); list->next = new ListNode(2); list->next->next = new ListNode(3); std::cout << "Before swap: "; printList(list); // 自己实现一个打印链表的函数 swapAdjacentNodes(list); std::cout << "After swap: "; printList(list); return 0; } ``` **对于双向链表：** ```cpp #include <iostream> struct Node { int val; Node* prev; Node* next; Node(int x) : val(x), prev(nullptr), next(nullptr) {} }; void swapAdjacentNodes(Node*& head) { if (head == nullptr || head->next == nullptr) return; Node* temp = head->next; head->next = temp->next; temp->next->prev = head; if (temp->next != nullptr) temp->next->prev = temp; else head->prev = temp; // 确保旧头结点的前驱指向新尾结点 temp->prev = head->prev; head->prev->next = temp; } // 示例如何使用 int main() { Node* list = new Node(1); list->prev = nullptr; list->next = new Node(2); list->next->prev = list; list->next->next = new Node(3); list->next->next->prev = list->next; std::cout << "Before swap: "; printList(list); // 自己实现一个打印链表的函数 swapAdjacentNodes(list); std::cout << "After swap: "; printList(list); return 0; } ``` 请注意，`printList`函数需要你自己实现，用于遍历并打印链表。