题目一：在O(1)时间内删除链表节点。
给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。
参考答案
class ListNode {
int value;
ListNode next;
}
public void deleteNode(ListNode head, ListNode toBeDeleted) {
if (head == null || toBeDeleted == null) {
return;
}
if (toBeDeleted.next != null) {
// 要删除的节点不是尾节点
ListNode pNext = toBeDeleted.next;
toBeDeleted.value = pNext.value;
toBeDeleted.next = pNext.next;
pNext = null;
} else if (head == toBeDeleted) {
// 链表只有一个节点，删除头节点（也是尾节点）
head = null;
toBeDeleted = null;
} else {
// 链表中有多个节点，删除尾节点
ListNode node = head;
while (node.next.next != null) {
node = node.next;
}
node.next = null;
toBeDeleted = null;
}
}
复杂度分析
- 时间复杂度：O(1)。
- 空间复杂度：O(1)。
题目二：删除链表中重复的节点。
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
练习地址
https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef
参考答案
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
ListNode pre = null, node = pHead;
while (node != null) {
boolean needDelete = false;
if (node.next != null && node.next.val == node.val) {
needDelete = true;
}
if (needDelete) {
int value = node.val;
while (node != null && node.val == value) {
node = node.next;
}
if (pre == null) {
pHead = node;
} else {
pre.next = node;
}
} else {
pre = node;
node = node.next;
}
}
return pHead;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
