简单

（待补充）

中等

复制带随机指针的链表

Leetcode No.138 复制带随机指针的链表

执行用时：16ms 打败85%

理解题意：深拷贝什么意思？

复制一个结点head，若通过语句Node dup = head，这样就是浅拷贝，只是复制了一个引用变量dup，两个引用变量dup和head指向同一个结点对象。

深拷贝则是复制出一个完全一样的独立的结点对象，深拷贝一个结点head，则必须创建另一个完全一样的独立的新结点对象dup，且head的next和random指向的结点也需要深拷贝到dup的next和random上。
即，若原链表有n个结点，则深拷贝得到的链表有且仅有n个对应的独立的结点副本。

我们使用迭代的方法，思路如下：

  1. 遍历原链表的每个结点，对每个结点进行深拷贝。
  2. 第一次遍历把每个结点的副本对象创建出来，并把next引用变量设置好。同时把已创建好的结点用哈希表记录，防止重复创建。
  3. 第二次遍历把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
26
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return head;

        unordered_map<Node*, Node*> map; 
        Node *ans = new Node(-1);
        Node *p, *q;
        p = ans, q = head;

        while(q) {
            Node *cur = new Node(q->val);  //仅把值传入，相当于新建一个新的节点，准备深拷贝
            map[q] = cur;  // 加入哈希表中
            p->next = cur;  //链表中加入新节点
            q = q->next;
            p = cur;
        }
        q = head;
        while(q) {
          	// 借助q找到其在哈希表中的位置 解决链表不可随机读取的问题
            map[q]->random = map[q->random];  // 设置指向
            q = q->next;
        }
        return ans->next;
    }
};

环形链表II

Leetcode No.142 环形链表II

执行用时：20ms 打败16%

我看一些时间复杂度中等的方法用的是快慢指针的办法，包括之前写的其实也是快慢指针，不过没有完成。然后昨天做了第138题，打开了哈希表新思路，不过时间复杂度比较差，代码是很简短的。

思路如下：

  1. 如果链表中存在回路，那么这个节点一定已经事先存储在了哈希表的内部了。
  2. 因此，在遍历链表内元素的时候，依次判断该节点是否加入了哈希表。没有的话就加入，没有话就直接返回该节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head) return NULL;

        unordered_map<ListNode*, int> map;
        
        ListNode *cur = head;
        int count = 0;
        while(cur) {
            // cur不在哈希表内 第一次出现
            if(map.find(cur) == map.end()) {
                map[cur] = count;
                ++count;
                cur = cur->next; 
            } else {
                return cur;
            }
        }
        return NULL;
    }
};

困难

(待补充)