题目描述

给定一个单向链表的节点p，但是不是头节点，并且保证链表中确实存在该节点，要求在O(1)时间复杂度内删除该节点p。你不能直接访问链表的头节点，只能访问和修改节点p及其后继节点（如果存在）。

解题思路

由于题目要求在O(1)时间复杂度内删除节点，且不能直接访问头节点，一个常见的技巧是将要删除的节点p的下一个节点的值复制到p中，然后删除p的下一个节点（即将p的next指针指向p->next->next），从而达到“删除”p的效果。注意，这种方法仅适用于非尾节点的情况，因为尾节点没有后继节点。但题目已保证p不是头节点，并且链表中确实存在该节点，所以这里不考虑尾节点的情况。

示例代码

PHP

class ListNode {
    public $val;
    public $next;
    
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function deleteNode($p) {
    // 假设p不是尾节点
    $p->val = $p->next->val;
    $p->next = $p->next->next;
}

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteNode(p):
    # 假设p不是尾节点
    p.val = p.next.val
    p.next = p.next.next

JavaScript

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function deleteNode(p) {
    // 假设p不是尾节点
    p.val = p.next.val;
    p.next = p.next.next;
}

码小课

码小课网站中有更多关于链表操作、算法设计、数据结构等相关内容分享给大家学习，涵盖从基础到进阶的各类知识点，帮助大家深入理解并掌握编程的核心技能。通过丰富的示例和详细的解析，让你在编程的道路上越走越远。