MENU

LeetCode237. Delete Node in a Linked List(模拟 / 链表)

2019 年 03 月 04 日 • 阅读: 1058 • LeetCode阅读设置

LeetCode237. Delete Node in a Linked List(模拟 / 链表)

  • Easy
  • Accepted:265,570
  • Submissions:510,572

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list -- head = [4,5,1,9], which looks like following:

img

Example 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.

Example 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.

Note:

  • The linked list will have at least two elements.
  • All of the nodes' values will be unique.
  • The given node will not be the tail and it will always be a valid node of the linked list.
  • Do not return anything from your function.

链接

https://leetcode.com/problems/delete-node-in-a-linked-list

题意

给定单链表的一个结点,要求在链表中删除该结点。保证该链表至少有两个结点,每个结点的值唯一,要求删除的结点不是尾结点。

题解

删除一个结点通俗的做法是找到该结点的前一个结点,然后让其指向该结点的下一个结点,但是这道题只给了要删除的结点,我们没法找到它的前一个结点,所以需要改变一下想法。

我们可以不删除这个结点,而是让这个结点保存下一个结点(它指向的)的信息然后“删除下一个结点”。这样就算完成题目要求了。

看讨论区说这道题有点智障。

代码

Time SubmittedStatusRuntimeMemoryLanguage
a few seconds agoAccepted20 ms9.2 MBcpp
2 minutes agoAccepted12 ms9.3 MBcpp
// 12 ms

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val; // 保存下一个结点的信息
        node->next = node->next->next; // “删除下一个结点”
    }
};
// 20ms

class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* next = node->next;
        node->val = next->val;
        node->next = next->next;
        delete next;
    }
};

第二种写法果然是比第一种要慢些。

事实上还有一种更简单的写法,来自讨论区大佬,我说我看了半天没看懂,原来是因为->成员选择(指针)的运算符优先级比*取值运算符高。所以实际上就是*node = *(node->next);,还是将下一个结点复制给当前结点。

void deleteNode(ListNode* node) {
    *node = *node->next;
}

The end.
2019年3月4日 星期一
最后编辑于: 2020 年 04 月 24 日