题目描述

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

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

解法一

思路

注意这题没有限定结点的值不能修改,而且直接给出需要删除的结点本身,而不是其值。那么这就有一个猥琐的办法了:

  1. 将当前结点值修改为【后一结点】值;
  2. 删除【后一结点】。

1 -> 2 -> 3 -> 4中删除3为例:

  1. 1 -> 2 -> 4 -> 4
  2. 1 -> 2 -> 4

回头想想,为什么要绕一圈删除【后一结点】而不是当前结点本身呢?因为题目中给的链表是单链表,当前结点只有next指针指向其【后一结点】,即只能修改当前结点之后的链表结构,所以为了简便起见,就拿【后一结点】开刀了。

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

C++

/**
 * 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;
    }
};