0%

[Leetcode]237. Delete Node in a Linked List(C++)

题目描述

题目链接:237. Delete Node in a Linked List

Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.

例子

例子 1

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation:
You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after > calling your function.

例子 2

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation:
You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

例子 3

Input: head = [1,2,3,4], node = 3
Output: [1,2,4]

Constraints

The number of the nodes in the given list is in the range [2, 1000].
-1000 <= Node.val <= 1000
The value of each node in the list is unique.
The node to be deleted is in the list and is not a tail node

解题思路

这道题要求删除链表中的一个节点,如果给定的是头节点的话,思路很简单,遍历至要被删除的节点的前一个节点将其指向要删除的节点的下一个节点即可。但这道题给定的是要被删除的节点,所以我们没办法改变前一个节点的指向(单向链表),但我们可以通过和下一个节点的值交换,将待删除节点变为下一节点,然后常规操作即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
};
  • 时间复杂度: O(1)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 237.DeleteNodeInALinkedList.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions