【复习36-37题】【每天40分钟，我们一起用50天刷完 (剑指Offer)】第二十七天 27/50

**复习36-37题**

**每天40分钟，我们一起用50天刷完 (剑指Offer)****第二十七天27/50**

---

###今日内容概述今天我们将继续学习剑指Offer的第36题和第37题。这些题目主要涉及数组和链表的操作，包括查找、插入、删除等基本操作。

### 第36题：从链表中删去指定节点**题目描述**

给定一个单向链表的头指针 `head`，以及一个要被删除的节点 `node`。请在 O(1) 空间复杂度下删除该节点。

**示例**

输入:`head = [4,5,3,2,1], node =3`
输出:`[4,5,1,2]`

### 第37题：合并两个有序链表**题目描述**

给定两个有序链表 `l1` 和 `l2`，请将它们合并为一个新的有序链表，并返回其头指针。合并后的链表应保持原来的有序性。

**示例**

输入:`l1 = [1,2,3], l2 = [4,5,6]`
输出:`[1,2,3,4,5,6]`

###代码实现#### 第36题：从链表中删去指定节点

cpp// Definition for singly-linked list.
struct ListNode {
 int val;
 ListNode *next;
 ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
 ListNode* deleteNode(ListNode* head, ListNode* node) {
 // 如果链表为空，则直接返回空指针 if (head == NULL) return NULL;

 // 如果要删除的节点是头结点 if (head == node) {
 // 如果链表只有一个节点，则直接返回NULL if (node->next == NULL) return NULL;
 // 否则，将下一个节点设为新头结点 else head = head->next;
 } // 如果要删除的节点不是头结点 else {
 // 找到前驱节点 ListNode* prev = head;
 while (prev->next != node) prev = prev->next;
 // 将要删除的节点设为其前驱的下一个节点 prev->next = node->next;
 }

 return head;
 }
};

cpp// Definition for singly-linked list.
struct ListNode {
 int val;
 ListNode *next;
 ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
 // 创建一个新链表的头结点 ListNode dummy(0);
 ListNode* head = &dummy;
 ListNode* p1 = l1;
 ListNode* p2 = l2;

 while (p1 != NULL && p2 != NULL) {
 if (p1->val < p2->val) {
 // 将较小的节点设为新链表的下一个节点 head->next = p1;
 p1 = p1->next;
 } else {
 // 将较大的节点设为新链表的下一个节点 head->next = p2;
 p2 = p2->next;
 }
 // 移动到下一个节点 head = head->next;
 }

 if (p1 != NULL) head->next = p1;
 else head->next = p2;

 return dummy.next;
 }
};