31天刷完剑指offer——(第2天) 链表

#pragma once
#include<vector>
#include<stack>

using std::vector;
using std::stack;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
/* (先反转链表(迭代)后打印)

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        ListNode* p = head, * q = head;         // p为原链表head，q为反转链表的headf （q起始为head，即原链表第一个头节点）

        while (p != nullptr) {                  // 遍历整个原链表
            if (p == head) {                    // 如果是原链表第一个头节点，要特殊处理
                p = p->next;                    // p先向后移动指向原链表下一个结点（即第二结点）
                q->next = nullptr;              // q->next==nullptr（即将原链表的第一个头节点 作为此时反转链表的头节点，也是尾结点，next为nullptr）
                continue;
            }
            
            ListNode* t = p->next;              // 保存原链表中p->next（即p指向结点的下一个结点地址）
            p->next = q;                        // 关键: 这一步将原链表p指向结点 指向反转链表头节点q，从而p指向结点变为 反转链表的头结点 （每次循环都将原链表中的头节点p 转移到反转链表中）
            q = p;                              // 此时反转链表头节点q为 原链表头节点p
            p = t;                              // 转移后的 原链表头节点为 t指向的结点
        }

        vector<int> vec;
        while (q != nullptr) {                  // 遍历反转后的链表 并逐个将值val插入到vec中
            vec.push_back(q->val);
            q = q->next;
        }
        return vec;
        
    }
};


*/


// 使用栈
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        stack<int> stk;
        while (head != nullptr) {           // 顺序遍历链表，将每个结点值 push到栈stk中
            stk.push(head->val);
            head = head->next;
        }

        vector<int> vec;
        while (!stk.empty()) {
            vec.push_back(stk.top());       // 利用栈的特性，将栈中的元素出栈 并存储在vec中
            stk.pop();
        }

        return vec;
    }
};

剑指offer 24. 反转链表 (easy)

#pragma once
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}

};


/* (迭代)

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* p = nullptr;

        while (head != nullptr) {               // 遍历整个原链表
            ListNode* t = head->next;           // 保存原链表中head->next（即head指向结点的下一个结点地址）
            head->next = p;                     // 关键: 这一步将原链表head指向结点 指向反转链表头节点p，从而head指向结点变为 反转链表的头结点 （每次循环都将原链表中的头节点head 转移到反转链表中）
            p = head;                           // 此时反转链表头节点p为 原链表头节点head
            head = t;                           // 转移后的 原链表头节点为 t指向的结点
        }

        return p;
    }
};

*/


// (递归)
class Solution {
private:
    ListNode* rhead;        // 用来记录反转链表后的头节点，也就是原链表的尾结点

public:
    ListNode* dg(ListNode* head);
    ListNode* reverseList(ListNode* head) {
        dg(head);

        return rhead;
    }
     
};

ListNode* Solution::dg(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {         // 递归到最后一个结点返回 （注意链表为空的情况）
        rhead = head;                          // 记录原链表的尾结点（即反转链表的头节点）
        return head;
    }

    ListNode* head_next = dg(head->next);      // 函数dg返回的结点即head->next，即当前结点的下一个结点
    head_next->next = head;                    // 当前结点的下一个结点指向自己
    head->next = nullptr;                      // 自己的next设为nullptr （head此时是 当前反转链表的尾结点）
 
    return head;                               // 传进来是head，返回的也是head（该法的核心在于，必须从原链表尾部往前反转，而不能从原链表头部往后反转）
}

#pragma once
#include<unordered_map>
#include<iostream>

using std::unordered_map;

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};


/* 直接法 （先构造复制链表，再查找并设置random指针）

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* dummy = new Node(0);             // 复制的链表的dummy结点 （即head头节点的前一个结点）
        Node* cur = head;                      // cur指向当前结点
        Node* pre = dummy;                     // pre指向"当前复制链表"的最后一个结点，也就是下一个新结点p的前一个结点

        while (cur != nullptr) {               // 遍历整个原链表，构造复制的链表结点和next指针 （random指针无法在 构造链表的过程中 设置，因为random指向的结点 可能还未构造）
            Node* p = new Node(cur->val);           // new一个新结点p，其值val与原链表中对应的结点相同
            p->next = nullptr;                      // p的next设为nullptr （结点p将要是"当前复制链表"的尾结点）
            pre->next = p;                          // 将结点p接在"当前复制链表"尾部
            pre = p;                                // pre赋值为p，即向后移动 （因此pre又指向"当前复制链表"的最后一个结点）

            cur = cur->next;                        
        }

        for (Node* p = head, *q = dummy->next; p != nullptr; p = p->next, q = q->next) {      // p和q分别指向原链表和复制链表，同时遍历两条链表，设置复制链表的结点的random指针

            Node* random = p->random;                              // random为原链表中 p指向结点的random指针
            int distence = 0;
            for (Node* i = head; i != random; i = i->next) {       // 计算random指针指向的结点 离头节点的距离distence
                ++distence;
            }
            Node* j = dummy->next;
            while (distence != 0) {           // 根据距离distence在复制链表中 找到相应的结点的指针j
                j = j->next;
                --distence;
            }
            q->random = j;                    // 因此q指向结点 的random指针为j

        }

        return dummy->next;
    }
};

*/


/* 利用map存储 原链表结点指针和复制链表结点指针 的键值对 （相比上面方法更巧妙，无需计算距离和根据距离查找random，时间复杂度从N*N下降到N）

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> hash;

        for (Node* cur = head; cur != nullptr; cur = cur->next) {     // 遍历原链表
            Node* node_p = new Node(cur->val);                        // 先创建结点，并建立map中 原链表结点指针和复制链表结点指针 的映射关系
            hash[cur] = node_p;
        }

        for (Node* cur = head; cur != nullptr; cur = cur->next) {     // 遍历原链表
            hash[cur]->next = hash[cur->next];                        // 设置之前创建的 复制结点的next和random指针 （因为是复制链表，所以复制结点的next,random指针 指向结点的位置 与原链表相应结点的next,random指针指向结点位置 是相对应的）
            hash[cur]->random = hash[cur->random];                    // 根据原结点和复制结点的 这种映射关系，可以用来设置 复制结点的next和random指针 
        }

        return hash[head];
    }
};

*/


// 拼接+拆分（将复制结点插入 原链表中对应结点的后面，根据位置对应关系 并结合拼接链表，就能够通过一次遍历链表来设置 复制链表的结点的random，之后再拆分从而得到复制链表）
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }

        for (Node* cur = head; cur != nullptr; cur = cur->next->next) {          // 拼接（将复制结点插入原链表的 cur指向的结点后面）
            Node* node_p = new Node(cur->val);
            node_p->next = cur->next;
            cur->next = node_p;
        }

        for (Node* cur = head; cur != nullptr; cur = cur->next->next) {          // 设置复制链表的结点的random指针（根据位置对应关系 并结合拼接链表知: 复制结点的random即 "cur指向结点的random指针指向结点 之后的结点的指针"）
            if (cur->random != nullptr) {
                cur->next->random = cur->random->next;
            }
        }

        Node* pre = head, * cur = head->next, * copy_head = head->next;          // 拆分 （将原链表和复制链表拆分）
        while (pre->next->next != nullptr) {
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr;            // 注意！虽然我们返回的是复制链表，但是拆分后的 原链表的尾结点next指针必须设置为nullptr，否则会出错！

        return copy_head;
    }
};