題目一：在O(1)時(shí)間內(nèi)刪除鏈表節(jié)點(diǎn)腰湾。
給定單向鏈表的頭指針和一個(gè)節(jié)點(diǎn)指針，定義一個(gè)函數(shù)在O(1)時(shí)間內(nèi)刪除該節(jié)點(diǎn)。
參考答案
class ListNode {
int value;
ListNode next;
}
public void deleteNode(ListNode head, ListNode toBeDeleted) {
if (head == null || toBeDeleted == null) {
return;
}
if (toBeDeleted.next != null) {
// 要?jiǎng)h除的節(jié)點(diǎn)不是尾節(jié)點(diǎn)
ListNode pNext = toBeDeleted.next;
toBeDeleted.value = pNext.value;
toBeDeleted.next = pNext.next;
pNext = null;
} else if (head == toBeDeleted) {
// 鏈表只有一個(gè)節(jié)點(diǎn)缭裆，刪除頭節(jié)點(diǎn)（也是尾節(jié)點(diǎn)）
head = null;
toBeDeleted = null;
} else {
// 鏈表中有多個(gè)節(jié)點(diǎn)陈莽，刪除尾節(jié)點(diǎn)
ListNode node = head;
while (node.next.next != null) {
node = node.next;
}
node.next = null;
toBeDeleted = null;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(1)渤昌。
- 空間復(fù)雜度：O(1)。
題目二：刪除鏈表中重復(fù)的節(jié)點(diǎn)走搁。
在一個(gè)排序的鏈表中独柑，存在重復(fù)的結(jié)點(diǎn)，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)私植，重復(fù)的結(jié)點(diǎn)不保留忌栅，返回鏈表頭指針。 例如曲稼，鏈表1->2->3->3->4->4->5 處理后為 1->2->5
練習(xí)地址
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;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)索绪。
- 空間復(fù)雜度：O(1)。
