单链表就地逆置,输入值以-1结束,用C++代码
时间: 2024-10-08 12:15:57 浏览: 39
单链表就地逆置意味着我们不需要额外的空间,仅通过改变现有节点的指针就可以将链表反转。当遇到-1作为输入值时,可以视为链表的结束标志。以下是使用C++实现的简单代码:
```cpp
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr && curr->val != -1) {
// 保存当前节点的下一个节点
ListNode* temp = curr->next;
// 将当前节点的next指向prev
curr->next = prev;
// 更新prev和curr
prev = curr;
curr = temp;
}
return prev; // 返回新头节点,即原尾节点
}
void printList(ListNode* head) {
while (head != nullptr) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
int main() {
ListNode* list = new ListNode(1);
list->next = new ListNode(2);
list->next->next = new ListNode(3);
list->next->next->next = new ListNode(-1); // 标记结尾
cout << "Original List: ";
printList(list);
list = reverseList(list);
cout << "Reversed List: ";
printList(list);
return 0;
}
```
在这个例子中,`reverseList`函数接收一个链表头节点,遍历过程中每次迭代都更新当前节点和前驱节点,并在遇到-1时停止。最后返回新的头节点,整个链表就被就地反转了。
阅读全文