力扣刷题笔记——反转链表

本文介绍: 经典问题反转链表这里给出四种解法。

经典问题反转链表

这里给出四种解法

这种方法是用一个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;
    }
};

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; // 返回新链表的头部
    }
};

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; // 返回新链表的头部
    }
};

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; // 返回新链表的头部
    }
};

显示所有内容

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。