删除链表节点

2023-07-23 19:22| 来源: 网络整理| 查看: 265

题目一题目描述

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

链表节点与函数定义如下：

public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } ListNode(){} } void deleteNode(ListNode head, ListNode toBeDeleted); 解题思路

核心：当我们想删除一个节点时，并不一定要删除一个节点本身，可以先把下一个节点的内容复制出来覆盖被删除节点的内容，然后把下一个节点删除。

如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。如果该节点是尾节点，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 null，时间复杂度为 O(N)。

时间复杂度分析：如果进行 N 次操作，那么需要操作节点的次数为 N-1+N=2N-1，其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数，N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。(2N-1)/N 约等于 2，因此该算法的平均时间复杂度为 O(1)。

代码 public class DeleteNode { /** * 从链表中删除某个节点 * @param head 头节点 * @param toBeDeleted 要删除的节点 */ public static void deleteNode(ListNode head, ListNode toBeDeleted) { // 两个指针否要考虑非法输入 if(head == null || toBeDeleted == null) { return; } // 要删除的节点不是尾节点 if (toBeDeleted.next != null) { ListNode next = toBeDeleted.next; toBeDeleted.val = next.val; toBeDeleted.next = next.next; next = null; } else { // 要删除的节点是尾节点(只能遍历) ListNode current = head; while (current.next != toBeDeleted) { current = current.next; } current.next = null; } } // 测试 public static void main(String[] args) { ListNode listNode_1 = new ListNode(1); ListNode listNode_2 = new ListNode(2); ListNode listNode_3 = new ListNode(3); ListNode listNode_4 = new ListNode(4); listNode_1.next = listNode_2; listNode_2.next = listNode_3; listNode_3.next = listNode_4; print_listNode(listNode_1); // 删除前 deleteNode(listNode_1, listNode_1); print_listNode(listNode_1); // 删除后 deleteNode(listNode_1, listNode_3); print_listNode(listNode_1); // 再次删除后 } // 打印listNode(用作测试) public static void print_listNode(ListNode listNode) { while (listNode != null) { System.out.print(listNode.val+" "); listNode = listNode.next; } System.out.println(); } } 题目二题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

解题思路

定义两个指针（preNode，node），一个用来指向不被删除的前一个节点，一个用来遍历链表

定义删除标志，如果前后两个值相等就需要删除，不等就不需要删除，改变preNode

在删除的时候需要连续删除，还要考虑preNode是或否存在，如果不存在它就是头指针，因为在java中无法在方法中修改头结点，所以可以把下一节点nextNode的值给它，并且让头结点的next指向next.next

代码 public class DeleteDuplication { public static void deleteDuplication(ListNode head) { // 防止非法输入 if (head == null) { return; } // 定义两个指针 ListNode preNode = null; ListNode node = head; // 遍历链表 while (node != null) { ListNode next = node.next; boolean needDelete = false; if (next != null && next.val == node.val) { needDelete = true; } if (!needDelete) { preNode = node; node = next; } else { int value = node.val; ListNode toBeDeleted = node; while (toBeDeleted != null && toBeDeleted.val == value) { next = toBeDeleted.next; toBeDeleted = toBeDeleted.next; } // 如果是头指针，就把next的值给它，并且让它的next指向next.next if (preNode == null) { head.val = next.val; head.next = next.next; next.next = null; } else { preNode.next = next; } node = next; } } } // 测试 public static void main(String[] args) { ListNode listNode_1 = new ListNode(1); ListNode listNode_2 = new ListNode(1); ListNode listNode_3 = new ListNode(1); ListNode listNode_4 = new ListNode(4); ListNode listNode_5 = new ListNode(5); listNode_1.next = listNode_2; listNode_2.next = listNode_3; listNode_3.next = listNode_4; listNode_4.next = listNode_5; print_listNode(listNode_1); // 删除前 deleteDuplication(listNode_1); print_listNode(listNode_1); // 删除后 } // 打印listNode(用作测试) public static void print_listNode(ListNode listNode) { while (listNode != null) { System.out.print(listNode.val+" "); listNode = listNode.next; } System.out.println(); } }

来自：

《剑指Offer》

Coding-Interviews/删除链表节点.md at master · todorex/Coding-Interviews 源代码有问题，已提交Issue：https://github.com/todorex/Coding-Interviews/issues/7

【本文地址】

公司简介

联系我们