C++中反转链表的完整效率写法

唯·爱

1. C++中反转链表的完整效率写法
   
2. 
   
3. ```cpp
   
4. #include <iostream>
   
5. 
   
6. using namespace std;
   
7. 
   
8. // 链表节点定义
   
9. struct ListNode {
   
10.     int val;
    
11.     ListNode* next;
    
12.     ListNode(int x) : val(x), next(nullptr) {}
    
13. };
    
14. 
    
15. // 反转链表函数
    
16. ListNode* reverseList(ListNode* head) {
    
17.     ListNode* prev = nullptr;
    
18.     ListNode* curr = head;
    
19.    
    
20.     while (curr != nullptr) {
    
21.         ListNode* nextTemp = curr->next;
    
22.         curr->next = prev;
    
23.         prev = curr;
    
24.         curr = nextTemp;
    
25.     }
    
26.    
    
27.     return prev;
    
28. }
    
29. 
    
30. // 打印链表函数
    
31. void printList(ListNode* head) {
    
32.     ListNode* curr = head;
    
33.    
    
34.     while (curr != nullptr) {
    
35.         cout << curr->val << " ";
    
36.         curr = curr->next;
    
37.     }
    
38.     cout << endl;
    
39. }
    
40. 
    
41. int main() {
    
42.     // 创建链表 1->2->3->4->5
    
43.     ListNode* head = new ListNode(1);
    
44.     ListNode* node2 = new ListNode(2);
    
45.     ListNode* node3 = new ListNode(3);
    
46.     ListNode* node4 = new ListNode(4);
    
47.     ListNode* node5 = new ListNode(5);
    
48.    
    
49.     head->next = node2;
    
50.     node2->next = node3;
    
51.     node3->next = node4;
    
52.     node4->next = node5;
    
53.    
    
54.     // 打印原始链表
    
55.     cout << "Original List: ";
    
56.     printList(head);
    
57.    
    
58.     // 反转链表
    
59.     ListNode* reversedHead = reverseList(head);
    
60.    
    
61.     // 打印反转后的链表
    
62.     cout << "Reversed List: ";
    
63.     printList(reversedHead);
    
64.    
    
65.     return 0;
    
66. }
    
67. ```
    
68. 
    
69. 该代码首先定义了一个`ListNode`结构体，用于表示链表节点。然后定义了`reverseList`函数，该函数使用迭代的方式反转链表。在函数中，使用两个指针`prev`和`curr`分别指向前一个节点和当前节点，通过遍历链表，依次将当前节点的`next`指针指向前一个节点，然后更新`prev`和`curr`指针。最后返回`prev`指针，即为反转后的链表头节点。
    
70. 
    
71. 在`main`函数中，创建了一个包含5个节点的链表，并打印原始链表。然后调用`reverseList`函数反转链表，并打印反转后的链表。
    
72. 
    
73. 该算法的时间复杂度为O(n)，其中n为链表的长度。

复制代码