力扣刷题 | 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