21. Merge Two Sorted Lists

難度: Easy

類型: Linked list,Recursion 

CPP程式下載: 21.cpp

Topic:

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

 

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Consideration:

Linked List combined.

1. Compare and add the smaller one. Move pointer to next. When one list is ended, add the rest of another list.

2. If both lists empty, return nullptr.

Code:

/**

 * 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* list1, ListNode* list2) {

        //int iSize1=list1.size();

        //int iSize2=list2.size();

        //int i=0,j=0;

        ListNode* outlist=nullptr;

        ListNode* outlistHead=nullptr;

        ListNode* list1tmp=list1;

        ListNode* list2tmp=list2;

        if (list1==nullptr) {

            return list2;

        }

        else if (list2==nullptr) {

            return list1;

        }

        else

        {

            

            while (1) {

                if (list2->val<list1->val) {

                     if (outlistHead==nullptr) {

                         //cout << "list2->val=" << list2->val << "\n";

                         outlist=list2;

                         list2=list2->next;

                         outlistHead=outlist;

                     }

                     else {

                         //cout << "list2->val=" << list2->val << "\n";

                         

                         outlist->next=list2;

                         list2=list2->next;

                         outlist=outlist->next;

                     }

                }

                else {

                    if (outlistHead==nullptr) {

                        outlist=list1;

                         list1=list1->next;

                         outlistHead=outlist;

                    }

                    else {

                         outlist->next=list1;

                         list1=list1->next;

                         outlist=outlist->next;

                     }

                }

                if (list1==nullptr)

                {

                    outlist->next=list2;

                    //cout << "A:list2->val=" << list2->val << "\n";

                    return outlistHead;

                }

                else if (list2==nullptr)

                {

                    outlist->next=list1;

                    return outlistHead;

                }

            }

        }

    }

};

Result:
https://leetcode.com/problems/merge-two-sorted-lists/submissions/1831161763/

Accepted

208 / 208 testcases passed

tendchen

submitted at Nov 16, 2025 16:45

Runtime

0ms

Beats100.00%

Memory

19.58MB

Beats26.66%

 92. Reverse Linked List II

難度: Medium

類型: Linked List

CPP程式下載: 92.cpp

前情題要:

反向連結 --- 給定一個連結的 list, 一個左邊位址, 一個右邊位置, 左邊位置小於或等於右邊位置, 把這個連結的左邊位置到右邊位置的連結反向, 回傳結果。(能夠一輪就給答案嗎?)

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

 

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

 

Follow up: Could you do it in one pass?

思考方式:

stack 的先進後出特性, 剛好拿來做反向連結。

1. 為了不破壞原有的 link list, 所有 output link list 的成員都是 new 出來的。這種方式會花費比較多的記憶體空間。其實也有另一種方法是直接改在原本的 linked list 上, 有機會另一篇文章再寫。

2. 運算過程中, 在大於等於左邊位置, 卻還仍小於右邊位置之前, 這些 linked list 的成員都 push 進Stack裡, 直到等於右邊位置時, 把右邊位置的 linked list 放上output連結後, 把 stack 裡的內容一個一個 pop 出來, 直到 stack 為空。

3. 記得更新 input linked list pointer 與 output linked list pointer。每次設定完一個新的output成員後, 記得把 output pointer 指定到 next。

複雜度思考:

Time Complexity: Worst case: O( N )

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 11.24 MB, Beats: 38.10%

Accepted

44 / 44 testcases passed

tendchen

submitted at Nov 07, 2025 05:39

Runtime

0ms

Beats100.00%

Analyze Complexity

Memory

11.24MB

Beats38.10%

Analyze Complexity

Code

C++

/**
 * 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* reverseBetween(ListNode* head, int left, int right) {
        ListNode *out=nullptr;
        ListNode *cur_OutNode=nullptr;
        ListNode *cur_InNode;
        stack<ListNode> sListNode;
        cur_InNode=head;
        int i,j;
        for (i=1;;i++)
        {
            if (cur_InNode==nullptr) return out;
            if (i<left)
            {
                if (out==nullptr)
                {
                    out=(new ListNode(cur_InNode->val));
                    cur_OutNode=out;
                    cur_InNode=cur_InNode->next;
                }
                else
                {
                    cur_OutNode->next=(new ListNode(cur_InNode->val));
                    cur_OutNode=cur_OutNode->next;
                    cur_InNode=cur_InNode->next;
                }
            }
            else
            {
                if (i<right)
                {
                    sListNode.push(*cur_InNode);
                    cur_InNode=cur_InNode->next;
                    //cout << "push and then size=" << sListNode.size() << "\n";
                }
                else if (i==right)
                {
                    if (out==nullptr)
                    {
                        out=(new ListNode(cur_InNode->val));
                        cur_OutNode=out;
                        cur_InNode=cur_InNode->next;
                    }
                    else
                    {
                        cur_OutNode->next=(new ListNode(cur_InNode->val));
                        cur_OutNode=cur_OutNode->next;
                        cur_InNode=cur_InNode->next;
                    }
                    for (j=1;;j++)
                    {
                        if (sListNode.size()==0) break;
                        cur_OutNode->next=(new ListNode(sListNode.top().val));
                        cur_OutNode=cur_OutNode->next;
                        sListNode.pop();
                    }
                }
                else
                {
                    cur_OutNode->next=(new ListNode(cur_InNode->val));
                    cur_OutNode=cur_OutNode->next;
                    cur_InNode=cur_InNode->next;
                }

            }
        }
    }
};