删除链表节点 -- java
题目一
题目描述
在 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