LeetCode Hot100 LinkList

Posted on Edited on

Problem

k个一组翻转链表
https://leetcode.cn/problems/reverse-nodes-in-k-group/submissions/540674966/?envType=study-plan-v2&envId=top-100-liked

Solution

引入dummy节点避免对头节点的特殊处理，
pre->cur->next1->next2->next[k-1]->next => pre->next[k-1]->next2->next1->cur->next
通过pre找到cur和next节点，然后反转cur->next[k-1]链表并将反转后的链表连接到pre后面和next前面，更新pre指针，遍历整个链表
在pre为空或者剩余链表长度小于K时结束

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
51
52
53
54
55
56
/**
 * Definition for singly-linked list.
 * 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 *reverse(ListNode *end, ListNode *start)
    {
        ListNode *p = start;
        ListNode *pre = end;
        while (p != end)
        {
            ListNode *next = p->next;
            p->next = pre;
            pre = p;
            p = next;
        }

        return pre;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {

        ListNode dummy(0, head);
        ListNode *pre = &dummy;

        // if (k == 1) return head;

        while (pre)
        {
            ListNode *cur = pre->next;
            ListNode *next = cur;

            int i = 0;
            for (; i < k; i ++)
            {
                if (next == nullptr) break;
                next = next->next;
            }

            if (i != k) break;

            pre->next = reverse(next, cur);
            pre = cur;
        }

        return dummy.next;
    }
};

Problem

随机链表的复制
https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-100-liked

Solution

第一次遍历列表，忽略random指针，拷贝链表并使用map建立老节点和新节点对应关系，第二次遍历列表根据老节点新节点对应关系
初始化新链表的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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

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

class Solution {
public:
    Node* copyRandomList(Node* head) {

        unordered_map<Node *, Node *> old2new;

        Node *ret = nullptr;
        Node dummy(0, nullptr);
        Node *p_new = dummy.next;
        Node *pre = &dummy;
        Node *p = head;

        while (p)
        {
            pre->next = new Node(p->val);
            old2new[p] = pre->next;
            pre = pre->next;
            p = p->next;
        }
        p = head;
        p_new = dummy.next;
        while (p)
        {
            if (p->random)
                p_new->random = old2new[p->random];
            p = p->next;
            p_new = p_new->next;
        }

        return dummy.next;
    }
};

Problem

排序链表
https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-100-liked

Solution

总体采用合并两个有序链表的思路来做，每次遍历列表，合并相邻两个已排序链表，合并长度由1到len/2 + 1，刚开始合并相邻两个长度为1的链表，下一次合并相邻两个长度为2的链表，以此类推，每次需要找到需要合并的两个链表的头和尾，将尾指针next置空然后合并两个列表，将合并后的链表接到pre_tail后面，更新指针有一些细节要注意，详见代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
 * Definition for singly-linked list.
 * 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 *merge2SortedList(ListNode *head1, ListNode *head2)
    {
        ListNode dummy(0, nullptr);

        ListNode *p = &dummy;
        ListNode *p1 = head1, *p2 = head2;

        while (p1 && p2)
        {
            if (p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }

        p->next = p1 ? p1 : p2;

        return dummy.next;
    }

    ListNode* sortList(ListNode* head) {

        int list_len = 0;

        ListNode *p = head;

        while (p)
        {
            list_len ++;
            p = p->next;
        }
        ListNode dummy(0, head);

        for (int len = 1; len < list_len; len *= 2)
        {
            ListNode *cur = dummy.next;
            ListNode *pre_tail = &dummy;

            while (cur)
            {
                ListNode *tail1 = cur;
                ListNode *head2 = cur;

                for (int i = 0; i < len - 1 && tail1->next != nullptr; i ++)
                {
                    tail1 = tail1->next;
                }

                head2 = tail1->next;
                tail1->next = nullptr;
                ListNode *tail2 = head2;

                for (int i = 0; i < len - 1 && tail2 && tail2->next != nullptr; i ++)
                {
                    tail2 = tail2->next;
                }
                ListNode *next_head = tail2 ? tail2->next : nullptr;
                if (tail2)
                    tail2->next = nullptr;
                ListNode *merged = merge2SortedList(cur, head2);
                pre_tail->next = merged;

                if (tail1 && tail2)
                {
                    pre_tail = tail1->val >= tail2->val ? tail1 : tail2;
                }
                else
                {
                    pre_tail = tail1 ? tail1 : tail2;
                }

                cur = next_head;
            }

        }

        return dummy.next;
    }
};

Problem

合并k个升序链表
https://leetcode.cn/problems/merge-k-sorted-lists/?envType=study-plan-v2&envId=top-100-liked

Solution

分支，将k个升序链表分成两组，对这两组链表做k/2个升序链表的排序，合并两个排序后的链表

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
51
52
/**
 * Definition for singly-linked list.
 * 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 *merge2Lists(ListNode *head1, ListNode *head2)
    {
        ListNode dummy(0, nullptr);
        ListNode *p = &dummy, *p1 = head1, *p2 = head2;

        while (p1 && p2)
        {
            if (p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }

        p->next = p1 ? p1 : p2;

        return dummy.next;
    }

    ListNode *mergeLists(vector<ListNode *> &lists, int l, int r)
    {
        if (l > r) return nullptr;
        if (l == r) return lists[l];

        int mid = (l + r) / 2;

        return merge2Lists(mergeLists(lists, l, mid), mergeLists(lists, mid+1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergeLists(lists, 0, lists.size()-1);
    }
};

Problem

LRU 缓存
https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked

Solution

map存储key-node用于查找，双向链表由于处理LRU的移动节点操作

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Node
{
public:
    int key, value;

    Node *pre, *next;

    Node(int key_, int val_) : key(key_), value(val_), pre(nullptr), next(nullptr) {}
};

class LRUCache {
public:

    unordered_map<int, Node *> cache;
    Node head;
    Node tail;

    int cap;

    void removeNode(Node *node)
    {
        Node *pre = node->pre;
        Node *next = node->next;
        pre->next = next;
        next->pre = pre;
    }

    void moveToHead(Node *node)
    {
        removeNode(node);
        node->next = head.next;
        head.next = node;
        node->pre = &head;
        node->next->pre = node;
    }

    void deleteTail()
    {
        Node *node = tail.pre;
        node->pre->next = &tail;
        tail.pre = node->pre;
        cache.erase(node->key);
        delete node;
    }

    LRUCache(int capacity): head(0, 0), tail(0, 0) {
        cap = capacity;
        head.next = &tail;
        tail.pre = &head;
    }

    int get(int key) {

        if (cache.count(key))
        {
            Node *pnode = cache[key];
            moveToHead(pnode);
            return pnode->value;
        }
        return -1;
    }

    void put(int key, int value) {
        if (cache.count(key))
        {
            Node *pnode = cache[key];
            moveToHead(pnode);
            pnode->value = value;
        }
        else
        {
            if (cache.size() == cap)
            {
                deleteTail();
            }

            Node *pnode = new Node(key, value);
            pnode->next = head.next;
            pnode->pre = &head;
            head.next = pnode;
            pnode->next->pre = pnode;
            cache[key] = pnode;
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */