FilesExpand file tree

 master

/

RemoveDuplicatesFromSortedListII82.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

115 lines (102 loc) · 3.23 KB

 master

/

RemoveDuplicatesFromSortedListII82.java

Copy path

Top

File metadata and controls

• Code
• Blame

115 lines (102 loc) · 3.23 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

/**

* Given a sorted linked list, delete all nodes that have duplicate numbers,

* leaving only distinct numbers from the original list.

*

* For example,

* Given 1->2->3->3->4->4->5, return 1->2->5.

* Given 1->1->1->2->3, return 2->3.

*

*/

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode(int x) { val = x; }

* }

*/

public class RemoveDuplicatesFromSortedListII82 {

public ListNode deleteDuplicates(ListNode head) {

ListNode dummy = new ListNode(0);

dummy.next = head;

ListNode p = dummy;

boolean isDuplicate = false;

int dup = 0;

while (p.next != null && p.next.next != null) {

if (isDuplicate) {

do {

p.next = p.next.next;

} while (p.next != null && p.next.val == dup);

isDuplicate = false;

} else {

if (p.next.val != p.next.next.val) {

p = p.next;

} else {

isDuplicate = true;

dup = p.next.val;

}

}

}

return dummy.next;

}

/**

* https://discuss.leetcode.com/topic/3890/my-accepted-java-code

*/

public ListNode deleteDuplicates2(ListNode head) {

if(head==null) return null;

ListNode FakeHead=new ListNode(0);

FakeHead.next=head;

ListNode pre=FakeHead;

ListNode cur=head;

while(cur!=null){

while(cur.next!=null&&cur.val==cur.next.val){

cur=cur.next;

}

if(pre.next==cur){

pre=pre.next;

}

else{

pre.next=cur.next;

}

cur=cur.next;

}

return FakeHead.next;

}

/**

* https://discuss.leetcode.com/topic/5206/my-recursive-java-solution

*/

public ListNode deleteDuplicates3(ListNode head) {

if (head == null) return null;

if (head.next != null && head.val == head.next.val) {

while (head.next != null && head.val == head.next.val) {

head = head.next;

}

return deleteDuplicates3(head.next);

} else {

head.next = deleteDuplicates3(head.next);

}

return head;

}

/**

* https://discuss.leetcode.com/topic/24470/java-simple-and-clean-code-with-comment

*/

public ListNode deleteDuplicates4(ListNode head) {

//use two pointers, slow - track the node before the dup nodes,

// fast - to find the last node of dups.

ListNode dummy = new ListNode(0), fast = head, slow = dummy;

slow.next = fast;

while(fast != null) {

while (fast.next != null && fast.val == fast.next.val) {

fast = fast.next; //while loop to find the last node of the dups.

}

if (slow.next != fast) { //duplicates detected.

slow.next = fast.next; //remove the dups.

fast = slow.next; //reposition the fast pointer.

} else { //no dup, move down both pointer.

slow = slow.next;

fast = fast.next;

}

}

return dummy.next;

}

}