力扣刷題 | 21、206、237與指針基本操作有關的簡單題

[21. 合并兩個有序連結清單]（尾插法）

将兩個升序連結清單合并為一個新的 升序 連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。

示例 ：

輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
           

限制：

兩個連結清單的節點數目範圍是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非遞減順序 排列
           

題解思路：疊代、遞歸

方法一：疊代

思路：依次将 l1 和 l2 連結清單中的節點放入建立的新頭節點後面。當一方周遊完畢後，可以将另一方剩餘節點直接接在傳回連結清單的後方。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		
        // 建立一個值為 -1 的節點
        // 并用一個指針 prev 進行尾接操作
        ListNode* prehead = new ListNode(-1);
        ListNode* prev = prehead;
	
        // 當 l1 和 l2 都未周遊完
        while (l1 != NULL && l2 != NULL) {
            if(l1->val < l2->val) {
                prev->next = l1;
                l1 = l1->next;
            }
            else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }
        
        // 當 l1 和 l2 有一方周遊完時
        if (l1 != NULL) prev->next = l1;
        else if (l2 != NULL) prev->next = l2;

        return prehead->next;
    }
};

// 通過
執行用時：4 ms
記憶體消耗：14.5 MB
           

方法二：遞歸

思路：和疊代類似

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        
        //終止條件
        if (l1 == nullptr) return l2;
        else if(l2 == nullptr) return l1;
	
        //尾接值較小的元素
        if(l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

// 通過
執行用時: 4 ms
記憶體消耗: 14.5 MB
           

206. 反轉連結清單（頭插法）

給你單連結清單的頭節點

head

，請你反轉連結清單，并傳回反轉後的連結清單。

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
           

連結清單中節點的數目範圍是 [0, 5000]
-5000 <= Node.val <= 5000
           

思路：從原連結清單周遊取值，并從建立節點的頭部插入。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* list = new ListNode(-1);

        while(head != NULL){
            ListNode* temp = new ListNode();
            temp->val = head->val;
            head = head->next;

            temp->next = list->next;
            list->next = temp;
        }
        return list->next;
    }
};

// 通過
執行用時: 4 ms
記憶體消耗: 8.2 MB
           

237. 删除連結清單中的節點

請編寫一個函數，使其可以删除某個連結清單中給定的（非末尾）節點。傳入函數的唯一參數為 要被删除的節點 。

輸入：head = [4,5,1,9], node = 5
輸出：[4,1,9]
解釋：給定你連結清單中值為 5 的第二個節點，那麼在調用了你的函數之後，該連結清單應變為 4 -> 1 -> 9.
           

連結清單至少包含兩個節點。
連結清單中所有節點的值都是唯一的。
給定的節點為非末尾節點并且一定是連結清單中的一個有效節點。
不要從你的函數中傳回任何結果。
           

class Solution {
public:
    void deleteNode(ListNode* node) {
        
        //值覆寫
        node->val = node->next->val;
        //節點删除
        node->next = node->next->next;  
    }
};

// 通過
執行用時: 8 ms
記憶體消耗: 7.6 MB