leetcode82-Remove Duplicates from Sorted List II

题目

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

分析

要删除重复元素肯定要有一个结点标示被删除元素的前驱，所以还是用一个哨兵结点next指向头结点，然后遍历链表即可。用cur指针指向链表的头结点，然后不断比较cur和她的next结点的值是否一样，如果一样则不断后移cur，最终比较哨兵结点的next是否是cur，如果不是则说明中间的元素值都一样直接更新哨兵的 next指针为cur的next，如果是的话则说明相邻俩个元素值不一样，那么后移哨兵结点继续遍历即可

public class LinkNode {
	int val;
	LinkNode next;

	public LinkNode(int data) {
		this.val = data;
		this.next = null;
	}
}
public class LinkList {
	LinkNode head;
	public LinkList() {
		this.head = null;
	}
	public LinkNode getHead() {
		return this.head;
	}
	//添加元素
	public void addNode(int data) {
		LinkNode node = new LinkNode(data);
		if (this.head == null) {
			this.head = node;
		} else {
			LinkNode cur = this.head;
			while(cur.next != null) {
				cur = cur.next;
			}
			cur.next = node;
		}
	}
	//正序打印
	public void print(LinkNode node) {
		while(node != null) {
			System.out.print(node.val);
			System.out.print(" ");
			node = node.next;
		}
		System.out.println();
	}
	public void removeDup() {
		LinkNode dummy = new LinkNode(-1);
		dummy.next = this.head;
		LinkNode p = dummy;
		while(p.next != null) {
			LinkNode cur = p.next;
			while(cur.next != null && cur.val == cur.next.val) {
				cur = cur.next;
			}
			if(p.next == cur) {
				p = p.next;
			} else {
				p.next = cur.next;
			}
		}
		print(dummy.next);
	}
}
public class removeDuplicatesfromSortedListII {
	public static void main(String[] args) {
		LinkList list = new LinkList();
		list.addNode(1);
		list.addNode(2);
		list.addNode(3);
		list.addNode(3);
		list.addNode(4);
		list.addNode(4);
		list.addNode(5);
		list.removeDup();
	}
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70