6-146 逆置链表代码
时间: 2024-07-29 15:00:22 浏览: 43
在编程中,6-146 通常指的是LeetCode上的一个题目,要求你实现一个函数来逆置单链表。这里是一个简单的Python代码示例,使用迭代的方式来解决这个问题:
```python
# 定义链表节点
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head):
prev = None
curr = head
while curr:
# 保存当前节点的下一个节点
next_temp = curr.next
# 将当前节点的next指向前一个节点
curr.next = prev
# 更新前一个节点和当前节点
prev = curr
curr = next_temp
return prev # 返回新的头节点,原头节点变成尾节点
```
这段代码的工作原理是,遍历链表时,每次都将当前节点的`next`指向前一个节点,然后移动`prev`和`curr`到下一对节点,直到遍历完整个链表。最后返回`prev`作为新的头节点。
如果你需要了解更深入的代码实现细节、算法分析或者其他编程语言的版本,或者对这个题目有任何疑问,请告诉我,我会很乐意帮助解答。
相关问题
实现双向链表的逆置 C++完整代码
在C++中,我们可以使用迭代的方式来实现双向链表的逆置,因为只需要遍历链表一次即可。以下是完整的代码示例:
```cpp
#include <iostream>
// 定义双向链表节点结构体
struct Node {
int data;
Node* prev;
Node* next;
Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};
// 双向链表类
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
// 构造函数
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// 插入节点到链表尾部
void insert(int value) {
if (head == nullptr) {
head = tail = new Node(value);
} else {
Node* newNode = new Node(value);
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
// 逆置链表
void reverse() {
Node* current = head;
Node* temp = nullptr;
while (current != nullptr) {
temp = current->prev; // 保存当前节点的前驱节点
current->prev = current->next; // 更新当前节点的指向前驱为原后继
current->next = temp; // 更新当前节点的后继为原前驱
current = temp; // 移动到下一个节点
}
// 如果原始头节点未改变,则更新新头节点
if (temp != nullptr) {
head = temp->prev;
}
}
// 打印链表
void print() {
Node* temp = head;
while (temp != nullptr) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << "\n";
}
};
int main() {
DoublyLinkedList list;
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);
std::cout << "Original List:\n";
list.print();
list.reverse();
std::cout << "Reversed List:\n";
list.print();
return 0;
}
```
在这个例子中,我们首先创建了一个双向链表并插入了一些元素。然后调用`reverse`方法来逆置链表,最后打印出逆转后的链表。
用头插法实现链表逆置简单代码c++
头插法(Head Insertion)是一种常见的链表操作,用于将链表反转。以下是使用C++实现单向链表逆置的一个简短代码:
```cpp
#include <iostream>
// 定义链表节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr; // 初始化前驱指针为空
ListNode* current = head; // 初始化当前指针为头结点
while (current != nullptr) { // 当链表非空时
ListNode* nextTemp = current->next; // 保存当前节点的下一个节点
current->next = prev; // 将当前节点的next指向前一个节点
prev = current; // 更新前驱指针
current = nextTemp; // 移动到下一个节点
}
return prev; // 返回新链表的头节点
}
int main() {
ListNode* list = new ListNode(1);
list->next = new ListNode(2);
list->next->next = new ListNode(3); // 创建一个简单的链表
list->next->next->next = new ListNode(4);
std::cout << "Original List: ";
printList(list);
ListNode* reversed = reverseList(list);
std::cout << "\nReversed List: ";
printList(reversed);
return 0;
}
// 打印链表辅助函数
void printList(ListNode* node) {
while (node != nullptr) {
std::cout << node->val << " -> ";
node = node->next;
}
std::cout << "nullptr\n";
}
```
这段代码首先创建了一个链表,然后通过`reverseList`函数将其逆序,最后打印原链表和逆序后的链表。
阅读全文