Offer18_2（删除链表中重复节点）

发表于 | 分类于 ，

题目：

　　在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
例如，链表1->2->3->3->4->4->5 处理后为 1->2->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
public ListNode deleteDuplication1(ListNode pHead) {
	if (pHead == null || pHead.next == null) {
		return pHead;
	}
	ListNode preHead = null;
	ListNode curHead = pHead;
	while(curHead != null) {
		if (curHead.next != null && curHead.val == curHead.next.val) {
			int value = curHead.val;
			ListNode tempNode = curHead;
			while(tempNode != null && tempNode.val == value) {
				tempNode = tempNode.next;
			}
			if (curHead == pHead) {
				pHead = tempNode;
			}else {
				preHead.next = tempNode;
			}
			curHead = tempNode;
		}else {
			preHead = curHead;
			curHead = curHead.next;
		}
	}
	return pHead;
}

复杂度分析：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。