算法系列——在O(1)时间内删除链表结点

题目描述

给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间内删除该结点。

解题思路

分为三种情况： 1.删除的是头结点

直接返回 head.next 2.删除的是尾结点

这种情况下，只能从头开始遍历，找到尾结点的前驱

3.删除的是中间结点

如果是中间节点，比如说 4->5->6->7->8 删除6对应的结点， 我们可以先将7赋给6，然后再将next指针指向8，那么就可以在O(1) 时间内删除这个结点。

核心思路代码如下所示：

toBeDeleted.val= toBeDeleted.next.val; toBeDeleted.next = toBeDeleted.next.next;

程序实现

public class Solution { public ListNode deleteNode(ListNode head, ListNode toBeDeleted) { // 如果输入参数有空值就返回表头结点 if (head == null || toBeDeleted == null) { return head; } // 如果删除的是头结点，直接返回头结点的下一个结点 if (head == toBeDeleted) { return head.next; } // 下面的情况链表至少有两个结点 // 在多个节点的情况下，如果删除的是最后一个元素 if (toBeDeleted.next == null) { // 找待删除元素的前驱 ListNode tmp = head; while (tmp.next != toBeDeleted) { tmp = tmp.next; } // 删除待结点 tmp.next = null; } // 在多个节点的情况下，如果删除的是某个中间结点 else { // 将下一个结点的值输入当前待删除的结点 toBeDeleted.val= toBeDeleted.next.val; // 待删除的结点的下一个指向原先待删除下下个结点，即将待删除的下一个结点删除 toBeDeleted.next = toBeDeleted.next.next; } // 返回删除节点后的链表头结点 return head; } }