剑指Offer:删除链表中重复的节点

题目

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

分析

我们首先从头开始遍历整个链表,如果当前节点(pNode)和后一个节点(pNext)的值(val)相同,则他们都需要被删除。删除操作需要保证删除之后的链表依然是相连的,所以我们需要确保待删除节点的前一个节点(preNode)始终和下一个没有重复的节点链接在一起。

例如题目中的例子,当我们遍历到第一个3时(这时preNode指向节点2),因为两个3相连,这两个节点都是需要被删除。这时preNode需要和第一个值为4的节点相连。接下来由于值为4的两个节点也重复了,还是会被删除。所以最终preNode会和值为5的节点相连。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
if (pHead == null)
return null;
ListNode preNode = null;
ListNode pNode = pHead;
while (pNode != null) {
ListNode pNext = pNode.next;
boolean toBeDel = false;

if (pNext != null && pNode.val == pNext.val) // 判断是否要删除
toBeDel = true;

if (!toBeDel) {
preNode = pNode; // 如果不需要删除就往后遍历
pNode = pNext;
} else {
int value = pNode.val;
ListNode delNode = pNode;
while (delNode!=null && delNode.val==value) {
pNext = delNode.next;
delNode = null;
delNode = pNext;
}
}
if (preNode == null)
pHead = pNext;
else
preNode.next = pNext;
pNode = pNext;

}
return pHead;
}
}

PS:注意判断是否存在空指针