力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
经典问题反转链表
这里给出四种解法
1.双指针
这种方法是用一个next指针记录当前节点的下一个节点,一个pre指针记录当前节点的前一个节点。
只需要遍历一遍链表就可以完成链表的反转
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode*pre,*curr;
curr=head;
pre=nullptr;
while(curr){
ListNode*next=curr->next;
curr->next=pre;
pre=curr;curr=next;
}
return pre;
}
};
2.栈
这种方法使用了额外的堆栈空间,但能够有效地反转链表。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 如果链表为空或只有一个节点,直接返回原链表
if (!head || !head->next)
return head;
stack<ListNode*> stk; // 创建一个堆栈,用于存储链表节点
ListNode* curr = head; // 创建指针curr,用于遍历原始链表
// 将链表节点逐个压入堆栈
while (curr) {
stk.push(curr);
curr = curr->next;
}
ListNode* newhead = stk.top(); // 堆栈的顶部节点作为新链表的头部
curr = newhead;
// 从堆栈中弹出节点,并重新连接链表节点
while (!stk.empty()) {
curr->next = stk.top();
curr = curr->next;
stk.pop();
}
curr->next = nullptr; // 将新链表的尾部节点的next设为nullptr,结束链表
return newhead; // 返回新链表的头部
}
};
3.递归
利用函数的栈来辅助完成反转
基本思想是将原始链表的头部节点不断地移到新链表的尾部,从而实现链表的反转。这个方法不需要额外的堆栈空间,但需要小心处理链表节点的指针。函数将递归地反转链表,直到链表的末尾,然后返回新链表的头部。
首先将问题拆为两部分
1.反转头节点
2.反转头节点之外的所有节点
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 如果链表为空或只有一个节点,直接返回原链表
if (!head || !head->next)
return head;
//反转头节点外的所有节点
// 调用递归函数,将head->next作为新链表的头部
ListNode* newhead = reverseList(head->next);
//反转头节点
// 将head节点的下一个节点的下一个指针指向head,实现反转
head->next->next = head;
// 将head节点的下一个指针设为nullptr,结束新链表的尾部
head->next = nullptr;
return newhead; // 返回新链表的头部
}
};
4.哈希表
可以用一个哈希表来储存每个节点的前一个节点
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 如果链表为空或只有一个节点,直接返回原链表
if (!head || !head->next)
return head;
unordered_map<ListNode*, ListNode*> hash; // 创建哈希表,存储每个节点和它们的前一个节点
ListNode* curr = head; // 当前节点
// 构建哈希表
while (curr->next) {
hash.insert({curr->next, curr}); // 存储当前节点的下一个节点和当前节点的映射关系
curr = curr->next; // 移动到下一个节点
}
ListNode* newhead = curr; // 新链表的头部为原始链表的末尾
curr = newhead; // 重新将curr指向新链表的头部
// 根据哈希表中的映射关系重新连接节点的指针
while (curr) {
curr->next = hash[curr]; // 重新连接节点的next指针
curr = curr->next; // 移动到下一个节点
}
head->next = nullptr; // 将原始链表的头部的next设为nullptr,结束链表
return newhead; // 返回新链表的头部
}
};