Cinte's Leetcode Record
0%

Posted on Edited on In Disqus:
Symbols count in article: 1.6k Reading time ≈ 1 mins.

33. Search in Rotated Sorted Array

参考面试题 10.03. 搜索旋转数组

区别在于这题的数字不重复

First Time
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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int sz = nums.size();
        auto bias = binarySearch(nums, 0, sz - 1);
        int lo = 0, hi = sz;
        int mid;
        while(lo < hi)
        {
            mid = (lo + hi) / 2;
            if(nums[(mid + bias) % sz] < target)
            {
                lo = mid + 1;
            }else
            {
                hi = mid;
            }
        }
        return (nums[(hi + bias) % sz] == target) ? (hi + bias) % sz : -1;

    }
private:
    int binarySearch(vector<int>& nums, size_t lo, size_t hi)
    {
        int mid;
        while (lo < hi)
        {
            mid = (lo + hi) / 2;
            if (nums[mid] > nums[hi])
            {
                lo = mid + 1;
            }
            else
            {
                hi = mid;
            }
        }
        return hi;
    }
};

O(logN)

review
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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        int sz = nums.size();
        while(lo < hi)
        {
            int mid = (lo + hi) / 2;
            if(nums[mid] < nums[hi])
                hi = mid;
            else
                lo = mid + 1;
        }
        int bias = hi;
        lo = 0, hi = nums.size();
        while(lo < hi)
        {
            int mid = (lo + hi) / 2;
            if(nums[(mid + bias) % sz] > target)
                hi = mid;
            else if(nums[(mid + bias) % sz] == target)
                return (mid + bias) % sz;
            else
                lo = mid + 1;
        }
        return -1;
    }
};
review(20211030)
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:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while(lo < hi)
        {
            int mid = lo + (hi - lo) / 2;
            if(nums[mid] >= target)
            {
                if(target < nums[lo] && nums[mid] >= nums[lo])
                    lo = mid + 1;
                else
                    hi = mid;
            }
            else
            {
                if(target >= nums[lo] && nums[mid] < nums[lo])
                    hi = mid;
                else
                    lo = mid + 1;
            }
        }
        return nums[hi] == target ? hi : -1;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

121. Best Time to Buy and Sell Stock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;
        for(size_t i = 0; i < prices.size(); ++i)
        {
            if(prices[i] < minPrice)
            {
                minPrice = prices[i];
            }
            if(prices[i] - minPrice > maxProfit )
            {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }
};
Kadane’s Algorithm

所有的差就相当于前一天卖今天买，如果连续起来的话那就是i-1天买i天卖，i天买i+1天卖=i-1天买，i+1天卖。所以当到i时收益为负数时候。i之前的持有没有意义，我不如i天买，后面卖还有可能变正

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxCur = 0;
        int maxSoFar = 0;
        for(auto i = prices.begin() + 1; i != prices.end(); ++i )
        {
            maxCur = max(0, (*i - *(i-1)) + maxCur); // 当0 > 后面那个时候，肯定是负的了，而不买必定为0，所以利润至少为0
            maxSoFar = max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }
};
另一种思路
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MIN;
        int sell = 0;
        for(auto price : prices)
        {
            buy = max(buy, -price); // 使得购入的成本尽可能小，也就是负数尽可能大
            sell = max(sell, buy + price); // 使得卖出后的利润尽可能大
        }
        return sell;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.8k Reading time ≈ 2 mins.

22. Generate Parentheses

这道题很硬核的使用了多种递归的方法

递归 Brute Force
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
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        genrateAll(string(2*n, ' '), 0, ret);
        return ret;
    }
private:
    void genrateAll(string s, int pos, vector<string>& ret)
    {
        if(pos == s.size())
        {
            if(isValid(s))
                ret.push_back(s);
        }else
        {
            s[pos] = '(';
            genrateAll(s, pos + 1, ret);
            s[pos] = ')';
            genrateAll(s, pos + 1, ret);
        }
    }
    
    bool isValid(string s)
    {
        int count = 0;
        for(auto& ch : s)
        {
            if(ch == '(')
                ++count;
            else
                --count;
            
            if(count < 0) 
                return false;
        }
        return count == 0;
    }
};

枚举出所有情况，然后对每种情况判断是否是合法的括号对，用到了20. Valid Parentheses中的思路

BackTracking
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:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        backTracking(ret, 0, 0, "", n);
        return ret;
    }
private:
    void backTracking(vector<string>& ret, int open, int close, string s, int n)
    {
        if(s.size() == n*2)
        {
            ret.push_back(s);
            return;
        }
        
        if(open < n)
        {
            backTracking(ret, open + 1, close, s + "(", n);
        }
        if(open > close)
        {
            backTracking(ret, open, close + 1, s + ")", n);
        }
    }
};

仅仅当括号符合添加的条件时才添加这个括号。
当左括号小于N的时候，表示可以加左边括号，那就加，当左括号大于右边括号时，那就加上右边括号来闭合。

Closure Number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        if(n == 0) ret.push_back("");
        for(int c = 0; c < n; ++c)
        {
            for(auto& left : generateParenthesis(c))
                for(auto& right : generateParenthesis(n - c - 1))
                    ret.push_back("(" + left + ")" + right);
        }
        return ret;
    }
};

第一个 n == 0 时添加一个""是为了让他可以进入一次循环计算右边项而不是直接return
c = (2c + 1 - 0 - 1）/2
n - c - 1 = (2n - 2c - 1 - 1)/2

review : ()中间包裹c对括号，()右边再加上n-c-1对括号，总共n对括号

为什么不在()左边加呢? 答： 也行

Posted on Edited on In Disqus:
Symbols count in article: 483 Reading time ≈ 1 mins.

20. Valid Parentheses

Solution 太强了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> map{ {'(', ')'}, { '{', '}' }, { '[', ']' } };
        stack<char> st;
        if (s.size() % 2) return false;
        for (auto& ch : s)
        {
            if (ch == (st.size() ? map[st.top()] : '#'))
                st.pop();
            else
                st.push(ch);
        }
        if (st.size())
            return false;
        return true;

    }
};

Posted on Edited on In Disqus:
Symbols count in article: 487 Reading time ≈ 1 mins.

16. 3Sum Closest

refer 3sum
Solution 1( 2 points)
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:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int diff = INT_MAX;
        for(size_t i = 0; i < nums.size() && diff != 0; ++i)
        {
            int lo = i + 1, hi = nums.size() - 1;
            while(lo < hi)
            {
                int sum = nums[i] + nums[lo] + nums[hi];
                if(abs(sum - target) < abs(diff))
                {
                    diff = sum - target;
                }
                if(sum < target)
                    ++lo;
                else
                    --hi;
            }
        }
        return diff + target;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.6k Reading time ≈ 2 mins.

387. First Unique Character in a String

First Time
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> map;
        for(int i = 0; i < s.size(); ++i)
        {
            if(!map.emplace(s[i], i).second)
                map[s[i]] = -1; 
        }
        for(auto& ch : s)
        {
            if(map[ch] != -1)
                return map[ch];
        }
        return -1;
    }
};
Second Time

数组由于直接获取内存地址而不需要散列，是更快的O(N) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int firstUniqChar(string s) {
        int eng[26]{0};
        for(auto& ch : s)
        {
            eng[ch - 'a'] += 1;
        }
        int i = 0;
        for(auto& ch : s)
        {
            if(eng[ch - 'a'] == 1)
                return i;
            ++i;
        }
        return -1;
    }
};
##### 尝试只进入一次(还是很慢) 
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:
    int firstUniqChar(string s) {
        unordered_map<char, int> map;
        unordered_set<char> set;
        for(int i = 0; i < s.size(); ++i)
        {
            if(!set.emplace(s[i]).second)
            {
                map.erase(s[i]);
            }else
            {
                map[s[i]] = i;
            }
        }
        int j = map.size() ? map.begin()->second : -1;
        for (auto i = map.begin(); i != map.end(); ++i)
        {
            j = min(j, i->second);
        }
        return j;
    }
};
##### 第二次遍历只遍历哈希 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> map;
        for(int i = 0, sz = s.size(); i < sz; ++i)
        {
            if(map.count(s[i]))
                map[s[i]] = -1;
            else
                map[s[i]] = i;
        }
        int first = s.size();
        for(auto& [_, frq] : map)
            if(frq != -1 && frq < first)
                first = frq;
        return first == s.size() ? -1 : first;
    }
};
##### 用队列，避免了第二次遍历 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
思路与算法

我们也可以借助队列找到第一个不重复的字符。队列具有「先进先出」的性质，因此很适合用来找出第一个满足某个条件的元素。

具体地，我们使用与方法二相同的哈希映射，并且使用一个额外的队列，按照顺序存储每一个字符以及它们第一次出现的位置。当我们对字符串进行遍历时，设当前遍历到的字符为 cc，如果 cc 不在哈希映射中，我们就将 cc 与它的索引作为一个二元组放入队尾，否则我们就需要检查队列中的元素是否都满足「只出现一次」的要求，即我们不断地根据哈希映射中存储的值（是否为 -1−1）选择弹出队首的元素，直到队首元素「真的」只出现了一次或者队列为空。

在遍历完成后，如果队列为空，说明没有不重复的字符，返回 -1−1，否则队首的元素即为第一个不重复的字符以及其索引的二元组。

小贴士

在维护队列时，我们使用了「延迟删除」这一技巧。也就是说，即使队列中有一些字符出现了超过一次，但它只要不位于队首，那么就不会对答案造成影响，我们也就可以不用去删除它。只有当它前面的所有字符被移出队列，它成为队首时，我们才需要将它移除。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> map;
        queue<pair<char, int>> q;
        for(int i = 0, sz = s.size(); i < sz; ++i)
        {
            if(!map.count(s[i]))
            {
                map.emplace(s[i], i);
                q.emplace(s[i], i);
            }else
            {
                map[s[i]] = -1;
                while(!q.empty() && map[q.front().first] == -1)
                    q.pop();
            }
        }
        return q.empty() ? -1 : q.front().second;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

24. Swap Nodes in Pairs

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
/**
 * 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* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* point = head;
        ListNode* pre = new ListNode();
        pre->next = head;
        ListNode* newHead = head->next;
        while(point != nullptr && point->next != nullptr)
        {
            ListNode* n2 = point->next;
            ListNode* next = n2->next;
            n2->next = point;
            point->next = next;
            pre->next = n2;
            pre = point;
            point = next;
        }
        return newHead;
    }
};
discussion 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 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* swapPairs(ListNode* head) {
        if(head == nullptr || head->next ==nullptr) return head;
        ListNode* n = head->next;
        head->next = swapPairs(head->next->next);
        n->next = head;
        return n;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 3.1k Reading time ≈ 3 mins.

912. Sort an Array

QuickSort
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
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        sort(nums, 0, nums.size() - 1);
        return nums;
    }
private:
    int patition(vector<int>& nums, int i, int j)
    {
        int pivot = rand() % (j - i + 1) + i;
        int c = nums[pivot];
        swap(nums[pivot], nums[i]);
        int lo = i, hi = j + 1;
        while(lo < hi)
        {
            while(lo < j && nums[++lo] < c) {}
            while(hi > i && nums[--hi] > c) {}
            if(lo >= hi)
                break;
            swap(nums[lo], nums[hi]);
        }
        swap(nums[hi], nums[i]);
        return hi;
    }
    void sort(vector<int>& nums, int i, int j)
    {
        if(i >= j)
            return;
        int m = patition(nums, i, j);
        sort(nums, i, m - 1);
        sort(nums, m + 1, j);
    }
};
mergeSort
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:
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
private:
    vector<int> tmp;
    void mergeSort(vector<int>& nums, int lo, int hi)
    {
        if(lo >= hi)
            return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        copy(nums.begin() + lo, nums.begin() + hi + 1, tmp.begin() + lo);
        int i = lo, j = mid + 1;
        int k = lo;
        while(i <= mid || j <= hi)
        {
            if(i == mid + 1)
                nums[k++] = tmp[j++];
            else if(j == hi + 1)
                nums[k++] = tmp[i++];
            else if(tmp[i] < tmp[j])
                nums[k++] = tmp[i++];
            else
                nums[k++] = tmp[j++];
        }
    }
};
heapSort
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
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        heapSort(nums);
        return nums;
    }
private:
    void adjustHeap(vector<int>& nums, int s, int m)
    {
        int tmp = nums[s];
        while((s << 1) + 1 <= m) // 如果左孩子存在，也就是这个点不是叶子节点
        {
            int lson = (s << 1) + 1; // 左孩子是当前节点*2+1
            int rson = (s << 1) + 2; // 右孩子是当前节点*2+2
            int large;
            if(nums[lson] > nums[s]) // 如果左孩子>父亲，large为左孩子
                large = lson;
            else                    // 反之，large为父亲
                large = s;
            if(rson <= m && nums[rson] > nums[large]) // 如果右孩子>父亲，large为右孩子
                large = rson;
            if(large != s) // 当large不是当前的点是，说明下面的树需要调整
            {
                swap(nums[large], nums[s]);
                s = large; // 将s调整为孩子，然后继续调整下面
            }else
                break;
        }
    }
    void heapSort(vector<int>& nums)
    {
        int sz = nums.size() - 1;
        for(int i = sz / 2; i >= 0; --i)
            adjustHeap(nums, i, sz);
        for(int i = sz; i >= 0; --i)
        {
            swap(nums[i], nums[0]);
            adjustHeap(nums, 0, --sz);
        }
    }
};
heapSort_review
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
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        HeapSort(nums);
        return nums;
    }

private:
    void PercolateDown(vector<int>& nums, int i, int len)
    {
        int child;
        for(; (i * 2 + 1) < len; i = child)
        {
            child = i * 2 + 1;
            if(child + 1 < len && nums[child + 1] > nums[child])
                ++child;
            if(nums[i] > nums[child])
                break;
            swap(nums[child], nums[i]);
        }
    }
    void BuildMaxHeap(vector<int>& nums)
    {
        int n = nums.size();
        for(int i = (n - 1) / 2; i >= 0; --i)
            PercolateDown(nums, i, n);
    }
    void HeapSort(vector<int>& nums)
    {
        int n = nums.size();
        BuildMaxHeap(nums);
        for(int i = n - 1; i >= 1; --i)
        {
            swap(nums[i], nums[0]);
            PercolateDown(nums, 0, --n);
        }
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.3k Reading time ≈ 2 mins.

34. Find First and Last Position of Element in Sorted Array

First Time
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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int size = nums.size();
        int lo = 0, hi = size - 1;
        int pos = -1;
        while(lo <= hi)
        {
            int medium = (hi + lo) / 2;
            if(nums[medium] < target)
            {
                lo = medium + 1;
            }else if(nums[medium] > target)
            {
                hi = medium - 1;
            }else
            {
                pos = medium;
                while (pos > 0 && nums[pos] == nums[pos - 1]) --pos;
                break;
            }
        }
        if(pos == -1) return {-1, -1};
        int i = pos + 1;
        while(i < size)
        {
            if(nums[i] != target)
                break;
            else
                ++i;
        }
        return {pos, i - 1};
    }
};
Second time
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:
    vector<int> searchRange(vector<int>& nums, int target) {
        int size = nums.size();
        int lo = 0, hi = size - 1;
        int posL = -1, posR = -1;
        while(lo <= hi)
        {
            int medium = (hi + lo) / 2;
            if(nums[medium] < target)
            {
                lo = medium + 1;
            }else if(nums[medium] > target)
            {
                hi = medium - 1;
            }else
            {
                posL = posR = medium;
                while (posL > 0 && nums[posL] == nums[posL - 1]) --posL;
                while (posR < size - 1 && nums[posR] == nums[posR + 1]) ++posR; 
                break;
            }
        }
        return {posL, posR};
    }
};
Solution
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:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = binarySearch(nums, target, true);
        if(left == nums.size() || nums[left] != target)
            return {-1, -1};
        return {left, binarySearch(nums, target, false) - 1};
    }
private:
    int binarySearch(vector<int>& nums, int target, bool isLeft)
    {
        int lo = 0, hi = nums.size();
        while(lo < hi)
        {
            int med = (lo + hi) / 2;
            if(nums[med] > target || (isLeft && nums[med] == target))
            {
                hi = med;
            }else
            {
                lo = med + 1;
            }
        }
        return lo;
    }
};
review
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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty())
            return {-1, -1};
        int lo = 0, hi = nums.size() - 1;
        while(lo < hi)
        {
            int mid = (lo + hi) / 2;
            if(nums[mid] < target)
                lo = mid + 1;
            else
                hi = mid;
        }
        if(nums[lo] != target)
            return {-1, -1};
        int left = lo;
        lo = 0;
        hi = nums.size() - 1;
        while(lo < hi)
        {
            int mid = (lo + hi) / 2 + 1;
            if(nums[mid] <= target)
                lo = mid;
            else
                hi = mid - 1;
        }
        return {left, hi};
            
    }
};

其中第一次往左找，第二次的mid+1是为了使mid偏向右边，从而找到最右的

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

21. Merge Two Sorted Lists

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
/**
 * 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* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1)
            return l2;
        if(!l2)
            return l1;

        while(l1 && l2)
        {
            if(l1->val > l2->val)
            {
                l2->next = mergeTwoLists(l1, l2->next);
                return l2;
            }else
            {
                l1->next = mergeTwoLists(l1->next, l2);
                return l1;
            }
        }
        return nullptr;
    }
};

迭代

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
/**
 * 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* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode ret;
        ListNode* head = &ret;
        while(l1 && l2)
        {
            if(l1->val > l2->val)
            {
                head->next = l2;
                l2 = l2->next;
            }
            else
            {
                head->next = l1;
                l1 = l1->next;
            }
            head = head->next;
        }
        head->next = l1 ? l1 : l2;
        return ret.next;
    }
};