LeetCode237. Delete Node in a Linked List（模拟 / 链表）

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:

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

题意

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

题解

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

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

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

代码

// 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日 星期一