Leetcode_20 天编程能力基础_day14

Posted on | In ,
| 7.9k | 1:06

继续，继续。

143. Reorder List

Analysis

按照题目给定的方式来重排链表，就是头一个，尾一个，交替排列。

Code

很容易想到用栈来保存倒序的链表，这样重排时就可以直接拿来用了。

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
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head->next) return;
        stack<ListNode*> st;
        ListNode *p = head;
        int cnt = 0;
        while(p) {
            st.push(p);
            cnt++;
            p = p->next;
        }
        p = head;
        for(int i = 1; i < cnt; i++) {
            if(i % 2) {
                ListNode *tmp = p->next;
                p->next = st.top();
                st.pop();
                p = p->next;
                p->next = tmp;
            } else p = p->next;
        }
        p->next = nullptr;
    }
};

时间复杂度：$O(n)$，空间复杂度：$O(n)$。
看了下官方题解，还有另外一种解法：将链表按照中间结点分成两部分，将后半部分链表翻转，然后合并两个子链表就可以得到结果了。
把原来写过的题的代码直接 copy 过来：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/* find middle node + reverse list + merge list */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head->next) return;
        ListNode *mid = middleNode(head);
        ListNode *L1 = head;
        ListNode *L2 = mid->next;
        mid->next = nullptr;
        L2 = reverseList(L2);
        mergeTwoLists(L1, L2);
    }
    ListNode* middleNode(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while(fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return nullptr;
        ListNode* L = new ListNode(0);
        ListNode *p = L, *t = L;
        while(head != nullptr) {
            t = head;
            head = head->next;
            t->next = p->next;
            p->next = t;
        }
        p = L;
        p = p->next;
        delete(L);
        return p;
    }
    void mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *p1;
        ListNode *p2;
        while(list1 != nullptr && list2 != nullptr) {
            p1 = list1->next;
            p2 = list2->next;
            
            list1->next = list2;
            list1 = p1;
            
            list2->next = list1;
            list2 = p2;
        }
    }
};

时间复杂度：$O(n)$，空间复杂度：$O(1)$，虽然优化了空间复杂度，但是好麻烦，有没有。
PS：空指针的判断最好不要用!，写成!= nullptr比较好。

138. Copy List with Random Pointer

Analysis

题目好长啊...
em…这个题如果对深拷贝和指针理解的比较清晰的话，应该很容易读懂题目要干什么。其实就是将原链表 copy 一份，但是新链表每个的 random 的值要变成新链表的对应结点的地址，需要注意的是新链表结点的相对位置与旧链表是一样的。

Code

method 1

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
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        unordered_map<Node*, int> ht;
        vector<Node*> nodes;
        Node *p = head;
        int index = 0;
        while(p) {
            ht[p] = index++;
            Node *node = new Node(p->val);
            nodes.push_back(node);
            p = p->next;
        }
        int indices[1005];
        memset(indices, -1, sizeof(indices));
        p = head;
        index = 0;
        while(p) {
            if(p->random != nullptr) indices[index] = ht[p->random];
            index++;
            p = p->next;
        }
        for(int i = 1; i < index; i++) {
            nodes[i - 1]->next = nodes[i];
        }
        for(int i = 0; i < index; i++) {
            if(indices[i] != -1) nodes[i]->random = nodes[indices[i]];
        }
        return nodes[0];
    }
};

这题太麻烦了，而且容易把人绕晕😵。因为 random 是个指针，所以为了知道原链表中每个结点中 random 到底指向的是当前链表的第几个结点，必须要将原链表结点的地址按照[address, index]的格式散列。然后再重新遍历原链表，这样就知道每个结点的 random 到底指向的是当前链表的第几个结点了。这样在复制好新链表后，这样重新遍历一次新链表就可以将所有新结点的 random 指针全部设置好。

仔细想想，有必要用 hash 来保存结点的地址与索引的映射吗？
直接按照旧结点与新结点地址的映射来保存不是更好吗？因为这样在遍历新链表的时候依然可以一次性修改所有新结点的 random 指针。

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
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        unordered_map<Node*, Node*> ht;
        vector<Node*> nodes;
        Node *p = head;
        int cnt = 0;
        while(p) {
            Node *node = new Node(p->val);
            node->random = p->random;
            ht[p] = node;
            nodes.push_back(node);
            p = p->next;
            cnt++;
        }
        for(int i = 0; i < cnt; i++) {
            nodes[i]->random = ht[nodes[i]->random];
        }
        for(int i = 1; i < cnt; i++) {
            nodes[i - 1]->next = nodes[i];
        }
        return nodes[0];
    }
};

再回头想想，之所以要用到 vector，是为了保存每个新结点，然后再遍历 vector 将新节点连成链表。有办法不用 vector，同时也将链表连起来吗？
回顾链表的建立，很容易会想到建立链表的几种方法：头插法、尾插法等，不过感觉最好用的还是带头（哑）结点的尾插法（链表建立的方法很多，叫法可能不一致，总之会就行了😂）。

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
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        unordered_map<Node*, Node*> ht;
        Node *L = new Node(INT_MAX);
        Node *p = head, *t = L;
        while(p) {
            Node *node = new Node(p->val);
            node->random = p->random;
            t->next = node;
            t = t->next;
            ht[p] = node;
            p = p->next;
        }
        t = L;
        L = L->next;
        delete(t);
        t = L;
        while(t) {
            if(ht.count(t->random)) t->random = ht[t->random];
            t = t->next;
        }
        cout << endl;
        return L;
    }
};

这个写完之后，其实可以发现前面写的代码有点问题。问题在于修改新链表的 random 时，没有先用 map 的 count 函数做判断，但依然可以提交通过。为什么呢？因为在之前的代码中，哈希表ht中没有保存 key 为nullptr 的键值对，在执行ht[nullptr] = xxx时，会自动添加这一项，但对应的 value 默认是0，而这个0与 C/C++ 的NULL和nullptr表示的值（仅就值而言）是一样的。所以，应该是编译器自动的将这个 0 转换为空指针赋给了 random（没错，g++ 会自己做强制类型转换，将赋值语句右边的变量类型转换为赋值语句左边的变量类型）。而巧合的是，复制这些新结点的旧结点的random本来就是nullptr 😂，所以是不影响结果的正确性的。

因为这个题只给了带参的构造函数，所以要带个参数😁。
看了一眼官方题解，果然，这种思路可以改成递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    unordered_map<Node*, Node*> ht;
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        if(!ht.count(head)) {
            Node *node = new Node(head->val);
            ht[head] = node;
            node->next = copyRandomList(head->next);
            node->random = copyRandomList(head->random);
        }
        return ht[head];
    }
};

说是递归，实际上是回溯 + 哈希的思路。

method 2

官方题解给的第二种思路，倒是挺有意思。以A->B->C->D为例，先改成A->A'->B->B'->C->C'->D->D'。这样改了之后，对于新链表而言，可以很容易的找到新链表结点之间与原链表结点之间一致的相对位置，也就是node->random->next。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    unordered_map<Node*, Node*> ht;
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        for(Node *node = head; node != nullptr; node = node->next->next) {
            Node *nodenew = new Node(node->val);
            nodenew->next = node->next;
            node->next = nodenew;
        }
        for(Node *node = head; node != nullptr; node = node->next->next) {
            Node *nodenew = node->next;
            nodenew->random = (node->random != nullptr) ? node->random->next : nullptr;
        }
        Node *headnew = head->next;
        for(Node *node = head; node != nullptr; node = node->next) {
            Node *nodenew = node->next;
            node->next = node->next->next;
            nodenew->next = (nodenew->next != nullptr) ? nodenew->next->next : nullptr;
        }
        return headnew;
    }
};

Summray

这两个与链表相关的中等题还有点意思，基本上可以想到做法，虽然可以通过，但不是比较优秀的解法。突然发现，中等题，好像就是把单一的知识点结合起来了。就像这两个题，既需要链表的知识，也需要哈希、栈的一些知识。所以，还是要见多识广。

Buy me a coffee ? :)
0%