【力扣】剑指offer第二天

[剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode）]

link

方法一

递归法

把整个链表从尾到头写入到一个数组里，比如，倒序1为头节点的链表，就要先把2为头节点的链表先倒序放到数组中，再把1节点push_back到数组中。2为头节点的链表倒序，就是先把3为头节点的链表倒序放到数组中，再把2节点push_back到数组中，依此类推

代码

int reverse_(ListNode* head,vector<int>&tmp)
{
    if(head->next==NULL)
    {
        return head->val;
    }
    tmp.push_back(reverse_(head->next,tmp));
    return head->val;
}

class Solution {
public:
    vector<int> reversePrint(ListNode* head) 
    {
        vector<int> tmp;
        if(head==NULL)
        return tmp;
        tmp.push_back(reverse_(head,tmp));
        return tmp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二

遍历链表，将节点的值放进数组中，再使用算法库提供的reverse()函数

代码

class Solution {
public:
    vector<int> reversePrint(ListNode* head) 
    {
        vector<int> tmp;
        ListNode* cur=head;
        while(cur)
        {
            tmp.push_back(cur->val);
            cur=cur->next;
        }
        reverse(tmp.begin(),tmp.end());
        return tmp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

[剑指 Offer 24. 反转链表 - 力扣（LeetCode）]

link

方法一

递归法

总体思路与上一道题的递归法思路一致

代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
           if(head==NULL||head->next==NULL)
           {
               return head;
           }
           ListNode* newnode=reverseList(head->next);
           head->next->next=head;
           head->next=NULL;
           return newnode;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二

进入循环前

第一次循环结束

第二次循环结束

第三次循环结束

第四次循环结束

第五次循环结束

代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* prev=NULL;
        ListNode* cur=head;
        while(cur)
        {
           ListNode* next=cur->next;
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

[剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode）]

link

方法一

两遍遍历：

第一遍遍历，创建节点，链接next，并且创建链表的每一个节点时，将被拷贝节点的地址和新创建节点的地址建立哈希

第二遍遍历，使用哈希表，通过原链表每一个节点中random的内容，映射到新链表对应的节点地址，写入新链表当前节点的random中

代码

class Solution {
public:
    Node* copyRandomList(Node* head) 
    {
        if(head==nullptr)
        {
            return nullptr;
        }

        unordered_map<Node*,Node*> _map;
        Node* _head=new Node(head->val);
        Node* prev=_head;
        Node* cur=head->next;
        _map[head]=_head;
        while(cur)
        {
            prev->next=new Node(cur->val);
            prev=prev->next;
            _map[cur]=prev;
            cur=cur->next;
        }
        cur=head;
        Node* _cur=_head;
        while(cur)
        {
            _cur->random=_map[cur->random];
            cur=cur->next;
            _cur=_cur->next;
        }
        return _head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

方法二

三遍遍历：

第一遍遍历

先将每一个节点，拷贝一份，接到被拷贝节点的后面，

第二遍遍历

拷贝节点的random指向的节点就是被拷贝节点的random指向的节点的下一个节点

第三遍遍历

拷贝节点拿出来形成一个新从链表

代码

class Solution {
public:
    Node* copyRandomList(Node* head) 
    {
        if(head==nullptr)
        {
            return nullptr;
        }
        unordered_map<Node*,Node*> _map;
        Node* _head=new Node(head->val);
        Node* prev=_head;
        Node* cur=head->next;
        _map[head]=_head;
        while(cur)
        {
            prev->next=new Node(cur->val);
            prev=prev->next;
            _map[cur]=prev;
            cur=cur->next;
        }
        cur=head;
        Node* _cur=_head;
        while(cur)
        {
            _cur->random=_map[cur->random];
            cur=cur->next;
            _cur=_cur->next;
        }
        return _head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31