发表更新LeetCode / 算法17 分钟读完 (大约2568个字)

LeetCode-13

1640. 能否连接形成数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        int arr_map[105] = {0};
        int len_arr = arr.size();
        for(int i = 0; i < len_arr; i++) {
            arr_map[arr[i]] = i+1;
        }
        int pie_len = pieces.size();
        for(int i = 0; i < pie_len; i++) {
            int i_len = pieces[i].size();
            int diff = arr_map[pieces[i][0]];
            if(diff == 0) {
                return false;
            }
            for(int j = 1; j < i_len; j++) {
                if(diff != arr_map[pieces[i][j]] - j) {
                    return false;
                }
            }
        }
        return true;
    }
};

4ms，和最快的思路刚好相反，用map存储arr的index，最快的思路是反过来，用map存一个piece的第一个index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        int arr_map[105] = {0};
        int len_arr = arr.size();
        int pie_len = pieces.size();
        for(int i = 0; i < pie_len; i++) {
            arr_map[pieces[i][0]] = i+1;
        }
        int i = 0;
        while(i < len_arr) {
            int row = arr_map[arr[i]];
            if(row == 0) return false;
            vector<int>& subv = pieces[row-1];
            int i_len = subv.size();
            for(int j = 0; j < i_len; j++, i++) {
                if(arr[i] != subv[j]) {
                    return false;
                }
            }
        }
        return true;
    }
};

707. 设计链表

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
struct List {
    List *next;
    int val;
    List(int val0, List* next0 = nullptr):val(val0), next(next0) {}
};

class MyLinkedList {
private:
    List *root;
    List *tail;
    int size;
    inline List* getNode(int& index) {
        List *move = root;
        while(index > 0 && move->next != nullptr) {
            move = move->next;
            index--;
        }
        return move;
    }
public:
    MyLinkedList() {
        root = new List(0);
        tail = root;
        size = 0;
    }
    
    int get(int index) {
        List *move = getNode(index);
        return (move->next == nullptr) ? -1 : move->next->val;
    }
    
    void addAtHead(int val) {
        List* node = new List(val, root->next);
        root->next = node;
        if(root == tail) {
            tail = node;
        }
        size++;
    }
    
    void addAtTail(int val) {
        List* node = new List(val, tail->next);
        tail->next = node;
        tail = node;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        List *move = getNode(index);
        if(index > 0) {
            return;
        }
        List* node = new List(val, move->next);
        move->next = node;
        if(move == tail) {
            tail = node;
        }
        size++;
    }
    
    void deleteAtIndex(int index) {
        List *move = getNode(index);
        List *target = move->next;
        if(target != nullptr)  {
            move->next = target->next;
            if(target == tail) {
                tail = move;
            }
            delete target;
            size--;
        }
    }
};
阅读更多
发表更新LeetCode / 算法11 分钟读完 (大约1618个字)

LeetCode-14

927. 三等分

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
class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        int sum = countOne(arr);
        int len = arr.size();
        if(sum % 3 != 0) {
            return {-1,-1};
        }
        if(sum == 0) {
            return {0, len -1};
        }

        int p1,p2,p3;
        p1 = p2 = p3 = 0;
        int i = 0;
        int cur = 0;
        while(i < len) {
            if(arr[i] == 1) {
                if(cur == 0) {
                    p1 = i;
                } else if(cur == sum/3) {
                    p2 = i;
                } else if(cur == 2*sum/3) {
                    p3 = i;
                }
                cur++;
            }
            i++;
        } //把1平均分成3份，p1 p2 p3分别找到三段的第一个1的位置
        // printf("%d %d %d\n", p1, p2, p3);
        int x = p1,y = p2,z = p3;
        int farclen = len - p3;
        if(p1 + farclen > p2 || p2 + farclen > p3) {
            return {-1, -1};
        }
        while(x < p2 && y < p3 && z < len) {
            if(arr[x] != arr[y] || arr[y] != arr[z]) {
                return {-1, -1};
            }
            x++;y++;z++;
        }
        // printf("%d %d %d\n", x, y, z);
        return {p1+farclen-1, p2+farclen};
    }
    int
     countOne(vector<int>& arr) {
        int count = 0;
        for(int a : arr) {
            count += a;
        }
        return count;
    }
};

难，看懂解析思路后才写出来的

刚开始的思路是找0，把1分成了n段，取n/3 , 2n/3和 n段后面的0，然后向右移动双指针比较

后来发现有超级长的输入，超时了

解析的思路与我刚好相反，先数1的个数，如果是0或者不能被3整除，说明不能分成三段

1的个数为n，找到第0 n/3 2n/3个1，记为p1, p2, p3

p3到后末尾的长度就是三个子串的长度，如果p1 或 p2 + 字串长度分别大于p2 p3，说明无解

然后向后比较，若后面的数完全相同则有解

阅读更多
发表更新LeetCode / 算法29 分钟读完 (大约4309个字)

LeetCode-15

904. 水果成篮

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
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int len = fruits.size();
        vector<int> v(len);
        int i = 0;
        int cur = fruits[i];
        i++;
        int max_diff = 1;
        int typea = fruits[0], typeb = -1, typec = -1;
        vector<int> last(len+1);
        int curr = 0;
        int j = 1;
        while(j < len) {
            while(j < len && fruits[j] == fruits[curr]) {
                j++;
            }
            last[j] = curr;
            curr = j;
            j++;
        }
        while(i < len) {
            int diff = 1;
            typeb = typec = -1;
            while(i < len) {
                if(fruits[i] != typea && fruits[i] != typeb) {
                    if(typeb == -1) {
                        typeb = fruits[i];
                    } else if(typec == -1) {
                        typec = fruits[i];
                    }
                }
                if(typec == -1) {
                    diff++;
                } else {
                    break;
                }
                i++;
            }
            max_diff = diff > max_diff ? diff : max_diff;
            if(i-1 >= 0 && i < len){
                typea = fruits[i-1];
                i = last[i]+1;
            }
        }
        return max_diff;
    }
};

想法很简单，就是从左往右遍历，数当前遇到了几种水果，当遇到第三种水果后，更新一下装入水果的最大值，三种水果记录为typea, typeb, typec
然后回溯，找到前一个节点在左侧最后一个typea后第一次出现的位置（其实也是typea最后出现的位置的后两个位置）

优化(空间，放弃last数组)

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
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int len = fruits.size();
        vector<int> v(len);
        int i = 0;
        int cur = fruits[i];
        i++;
        int max_diff = 1;
        int typea = fruits[0], typeb = -1, typec = -1;
        while(i < len) {
            int diff = 1;
            typeb = typec = -1;
            int lasta = i-1, lastb = 0;
            while(i < len) {
                if(fruits[i] != typea && fruits[i] != typeb) {
                    if(typeb == -1) {
                        typeb = fruits[i];
                    } else if(typec == -1) {
                        typec = fruits[i];
                    }
                }
                if(fruits[i] == typea) {
                    lasta = i;
                } else if(fruits[i] == typeb) {
                    lastb = i;
                }
                if(typec == -1) {
                    diff++;
                } else {
                    break;
                }
                i++;
            }
            max_diff = diff > max_diff ? diff : max_diff;
            if(i-1 >= 0 && i < len){
                if(fruits[i-1] == typea) {
                    i = lastb + 2;
                } else if(fruits[i-1] == typeb) {
                    typea = typeb;
                    i = lasta + 2;
                }
                // printf("%d, %d, %d\n", i, lasta, lastb);
            }
        }
        return max_diff;
    }
};

1441. 用栈操作构建数组

阅读更多
发表更新几秒读完 (大约34个字)

qq.md

我的QQ

1
2
3
"""
 -...  .-  .  -..  --.  ....  -.-.  .---  -...  -...
"""
发表更新算法2 分钟读完 (大约345个字)

LeetCode 524「通过删除字母匹配到字典里最长单词」

算法内容

本文件实现 LeetCode 524「通过删除字母匹配到字典里最长单词」的一种预处理做法。目标是在字典中找出可以由字符串 s 删除若干字符得到的最长单词；若长度相同，返回字典序最小者。

代码先构建 f[i][c]，表示从位置 i 开始往后字符 c 第一次出现的位置，不存在则为 m。匹配某个候选词时，只需按字符不断跳到下一个出现位置，如果任一字符不存在则匹配失败。这样可以把每个单词的匹配成本降为 O(单词长度)，预处理为 O(26m)。文件中带有打印矩阵的调试输出和一个示例调用。

算法实现

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
from typing import List, Tuple, Dict
class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        m = len(s)
        f = [[0] * 26 for _ in range(m)]
        f.append([m] * 26)
        print([chr(ord('a')+i) for i in range(26)])
        for i in range(m - 1, -1, -1):
            print('[', end='')
            for j in range(26):
                if ord(s[i]) == j + 97:
                    f[i][j] = i
                else:
                    f[i][j] = f[i + 1][j]
                print("'{}', ".format(f[i][j]), end='')
            print()
        res = ""
        for t in dictionary:
            match = True
            j = 0
            for i in range(len(t)):
                if f[j][ord(t[i]) - 97] == m:
                    match = False
                    break
                j = f[j][ord(t[i]) - 97] + 1
            if match:
                if len(t) > len(res) or (len(t) == len(res) and t < res):
                    res = t
        return res

print(Solution().findLongestWord("abpcplea", ["ale","apple","monkey","plea"]))

发表更新LeetCode / 算法29 分钟读完 (大约4307个字)

2022年10月17日

904. 水果成篮

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
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int len = fruits.size();
        vector<int> v(len);
        int i = 0;
        int cur = fruits[i];
        i++;
        int max_diff = 1;
        int typea = fruits[0], typeb = -1, typec = -1;
        vector<int> last(len+1);
        int curr = 0;
        int j = 1;
        while(j < len) {
            while(j < len && fruits[j] == fruits[curr]) {
                j++;
            }
            last[j] = curr;
            curr = j;
            j++;
        }
        while(i < len) {
            int diff = 1;
            typeb = typec = -1;
            while(i < len) {
                if(fruits[i] != typea && fruits[i] != typeb) {
                    if(typeb == -1) {
                        typeb = fruits[i];
                    } else if(typec == -1) {
                        typec = fruits[i];
                    }
                }
                if(typec == -1) {
                    diff++;
                } else {
                    break;
                }
                i++;
            }
            max_diff = diff > max_diff ? diff : max_diff;
            if(i-1 >= 0 && i < len){
                typea = fruits[i-1];
                i = last[i]+1;
            }
        }
        return max_diff;
    }
};

想法很简单，就是从左往右遍历，数当前遇到了几种水果，当遇到第三种水果后，更新一下装入水果的最大值，三种水果记录为typea, typeb, typec
然后回溯，找到前一个节点在左侧最后一个typea后第一次出现的位置（其实也是typea最后出现的位置的后两个位置）

优化(空间，放弃last数组)

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
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int len = fruits.size();
        vector<int> v(len);
        int i = 0;
        int cur = fruits[i];
        i++;
        int max_diff = 1;
        int typea = fruits[0], typeb = -1, typec = -1;
        while(i < len) {
            int diff = 1;
            typeb = typec = -1;
            int lasta = i-1, lastb = 0;
            while(i < len) {
                if(fruits[i] != typea && fruits[i] != typeb) {
                    if(typeb == -1) {
                        typeb = fruits[i];
                    } else if(typec == -1) {
                        typec = fruits[i];
                    }
                }
                if(fruits[i] == typea) {
                    lasta = i;
                } else if(fruits[i] == typeb) {
                    lastb = i;
                }
                if(typec == -1) {
                    diff++;
                } else {
                    break;
                }
                i++;
            }
            max_diff = diff > max_diff ? diff : max_diff;
            if(i-1 >= 0 && i < len){
                if(fruits[i-1] == typea) {
                    i = lastb + 2;
                } else if(fruits[i-1] == typeb) {
                    typea = typeb;
                    i = lasta + 2;
                }
                // printf("%d, %d, %d\n", i, lasta, lastb);
            }
        }
        return max_diff;
    }
};

1441. 用栈操作构建数组

阅读更多
发表更新LeetCode / 算法11 分钟读完 (大约1618个字)

2022年10月6日

927. 三等分

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
class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        int sum = countOne(arr);
        int len = arr.size();
        if(sum % 3 != 0) {
            return {-1,-1};
        }
        if(sum == 0) {
            return {0, len -1};
        }

        int p1,p2,p3;
        p1 = p2 = p3 = 0;
        int i = 0;
        int cur = 0;
        while(i < len) {
            if(arr[i] == 1) {
                if(cur == 0) {
                    p1 = i;
                } else if(cur == sum/3) {
                    p2 = i;
                } else if(cur == 2*sum/3) {
                    p3 = i;
                }
                cur++;
            }
            i++;
        } //把1平均分成3份，p1 p2 p3分别找到三段的第一个1的位置
        // printf("%d %d %d\n", p1, p2, p3);
        int x = p1,y = p2,z = p3;
        int farclen = len - p3;
        if(p1 + farclen > p2 || p2 + farclen > p3) {
            return {-1, -1};
        }
        while(x < p2 && y < p3 && z < len) {
            if(arr[x] != arr[y] || arr[y] != arr[z]) {
                return {-1, -1};
            }
            x++;y++;z++;
        }
        // printf("%d %d %d\n", x, y, z);
        return {p1+farclen-1, p2+farclen};
    }
    int
     countOne(vector<int>& arr) {
        int count = 0;
        for(int a : arr) {
            count += a;
        }
        return count;
    }
};

难，看懂解析思路后才写出来的

刚开始的思路是找0，把1分成了n段，取n/3 , 2n/3和 n段后面的0，然后向右移动双指针比较

后来发现有超级长的输入，超时了

解析的思路与我刚好相反，先数1的个数，如果是0或者不能被3整除，说明不能分成三段

1的个数为n，找到第0 n/3 2n/3个1，记为p1, p2, p3

p3到后末尾的长度就是三个子串的长度，如果p1 或 p2 + 字串长度分别大于p2 p3，说明无解

然后向后比较，若后面的数完全相同则有解

阅读更多
发表更新算法3 分钟读完 (大约397个字)

107. 二叉树的层序遍历 II

算法内容

本文件实现 LeetCode 107「二叉树的层序遍历 II」。核心思路是先按普通层序遍历从上到下收集每一层节点值，再对结果整体反转，得到自底向上的层序结果。

实现中使用两个队列：s 保存当前层待访问节点，tmp_s 暂存下一层节点。当前层队列清空时，将本层结果写入 res，再把下一层队列转为当前层继续处理。最后通过 reverse(res.begin(), res.end()) 将层序结果倒置。时间复杂度为 O(n)，每个节点访问一次；空间复杂度为 O(n)，主要来自队列和结果数组。

算法实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> s;
        if(root != nullptr) {
            s.push(root);
        }
        vector<vector<int>> res;
        vector<int> tmp;
        queue<TreeNode*> tmp_s;
        while(!s.empty()) {
            tmp.push_back(s.front()->val);
            TreeNode* tmp_node = s.front();
            if(tmp_node->left != nullptr) {
                tmp_s.push(tmp_node->left);
                // printf("add %d\n", tmp_node->left->val);
            }
            if(tmp_node->right != nullptr) {
                tmp_s.push(tmp_node->right);
                // printf("add %d\n", tmp_node->right->val);
            }
            s.pop();
            if(s.empty() && !tmp_s.empty()) {
                res.push_back(tmp);
                tmp.clear();
                while (!tmp_s.empty()){
                    s.push(tmp_s.front());
                    tmp_s.pop();
                }
            }
        }
        if(!tmp.empty()) {
            res.push_back(tmp);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};
发表更新算法3 分钟读完 (大约450个字)

146. LRU 缓存

算法内容

本文件实现 LeetCode 146「LRU 缓存」。目标是在固定容量下支持 get 和 put，并在容量满时淘汰最近最少使用的键。

代码使用 unordered_map<int, Node*> 做 key 到链表节点的映射，并用带哨兵节点 root 的双向循环链表维护访问顺序。链表头部表示最近使用，尾部表示最久未使用。get 命中后将节点移动到头部；put 已存在时更新值并移到头部，不存在且容量未满时插入新节点，容量已满时复用尾节点并更新映射。平均时间复杂度为 O(1)，空间复杂度为 O(capacity)。

算法实现

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
99
100
101
102
103
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>
using namespace std;

struct Node {
    int val;
    int key;
    Node* next;
    Node* last;
    Node(int val0, int key0, Node* next0=nullptr, Node* last0 = nullptr):key(key0), next(next0), val(val0), last(last0) {}
};
class LRUCache {
public:
    unordered_map<int, Node*> hash;
    Node* root;
    int size = 0;
    int capacity = 0;
    LRUCache(int capacity) {
        root = new Node(-1,-1);
        this->capacity = capacity;
        size = 0;
        root->last = root;
        root->next = root;
    }
    
    int get(int key) {
        Node* cur = hash[key];
        
        // printf("get %d\n", (cur==nullptr? -1 : (cur->val)));
        printAll();
        if(cur == nullptr) return -1;
        remove(cur);
        insertTop(cur);
        printAll();
        return cur->val;
    }
    
    void remove(Node*cur) {
        Node* last = cur->last;
        Node* next = cur->next;
        last->next = next;
        next->last = last;
    }

    void put(int key, int value) {
        // printf("put %d\n", value);
        printAll();
        if(hash[key] != nullptr) {
            Node* cur = hash[key];
            cur->val = value;
            remove(cur);
            insertTop(cur);
            // printf("replace :%d\n", cur->val);
        } else {
            if(size < capacity) {
                Node * cur = new Node(value, key);
                hash[key] = cur;
                insertTop(cur);
                size++;
                // printf("insert :%d\n", cur->val);
            } else {
                Node* cur = root->last;
                if(cur->key != -1){
                    hash[cur->key] = nullptr;
                    hash[key] = cur;
                    
                    cur->val = value;
                    cur->key = key;
                    remove(cur);
                    insertTop(cur);
                }
                // printf("lru :%d\n", cur->val);
            }
            
        }
        printAll();
    }
    void printAll() {
        // Node * cur = root->next;
        // while(cur != root) {
        //     printf("%d ", cur->val);
        //     cur = cur->next;
        // }
        // printf("\n");
    }
    void insertTop(Node* cur) {
        cur->last = root;
        cur->next = root->next;
        root->next->last = cur;
        root->next = cur;
    }
};

/**
 * 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);
 */
发表更新算法2 分钟读完 (大约364个字)

148. 排序链表

算法内容

本文件实现 LeetCode 148「排序链表」。核心思路是对单链表做归并排序，利用链表切分和有序链表合并完成排序。

split 使用快慢指针找到链表中点，并断开为左右两段；sortList 递归排序左右子链表；merge 使用虚拟头节点把两个有序链表合并。归并排序适合链表结构，因为合并时只需要调整指针，不需要随机访问。时间复杂度为 O(n log n)，递归栈空间复杂度为 O(log n)。

算法实现

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
/**
 * 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) {}
 * };
 */
#include <vector>
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
#include <unordered_map>
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) {}
};
using namespace std;
class Solution
{
public:
    ListNode *sortList(ListNode *head)
    {
        ListNode *left, *right;
        int len = split(head, &left, &right);
        if (len > 2)
        {
            left = sortList(left);
            right = sortList(right);
        }
        return merge(left, right);
    }

    ListNode *merge(ListNode *left, ListNode *right)
    {
        ListNode *head = new ListNode(0), *tmp;
        tmp = head;
        while (left != nullptr && right != nullptr)
        {
            if (left->val < right->val)
            {
                tmp->next = left;
                left = left->next;
            }
            else
            {
                tmp->next = right;
                right = right->next;
            }
            tmp = tmp->next;
        }
        if (left != nullptr)
        {
            tmp->next = left;
        }
        if (right != nullptr)
        {
            tmp->next = right;
        }
        tmp = head->next;
        return tmp;
    }

    int split(ListNode *head, ListNode **left, ListNode **right)
    {
        ListNode *v = new ListNode(0);
        v->next = head;
        ListNode *slow = v, *fast = v;
        int len = 0;
        while (fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
            len++;
            if (fast->next != nullptr)
            {
                fast = fast->next;
                len++;
            }
        }
        *left = head;
        *right = slow->next;
        slow->next = nullptr;
        return len;
    }
};

关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码6
Android车载1
Android面试查漏补缺2
C#9
C/C++1
CSharp9
Flutter1
Java基础 字节码2
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery6
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法69
×