C plus plus Linked List Inversion
时间: 2024-01-02 11:03:12 浏览: 25
链表反转是一道经典的算法问题,可以使用迭代或递归两种方法来实现。以下是使用迭代方法实现 C++ 链表反转的示例代码:
```cpp
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
while (curr != NULL) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
};
int main() {
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
Solution solution;
ListNode* newHead = solution.reverseList(head);
while (newHead != NULL) {
cout << newHead->val << " ";
newHead = newHead->next;
}
return 0;
}
```
在这个示例代码中,我们定义了一个 `ListNode` 结构体来表示链表节点,它包含一个整数 `val` 和指向下一个节点的指针 `next`。然后我们使用迭代方法实现了 `reverseList` 函数,该函数接受一个链表头指针 `head`,并返回一个新的链表头指针,该链表是输入链表的反转。
在 `reverseList` 函数中,我们定义了两个指针 `prev` 和 `curr`,分别指向当前节点的前一个节点和当前节点。然后我们使用一个 `while` 循环遍历整个链表,每次将当前节点的 `next` 指针指向前一个节点 `prev`,然后将 `prev` 指针指向当前节点 `curr`,将 `curr` 指针指向下一个节点 `nextTemp`。最后返回 `prev` 指针,它指向了反转后的链表头节点。
在 `main` 函数中,我们创建了一个包含四个节点的链表,并将其传递给 `reverseList` 函数进行反转。最后我们遍历反转后的链表并输出结果。