题目：
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.
链接： http://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
题解：
链表去重II，这里要建立一个fake head，因为假如全部为重复，需要移除所有的元素。 还需要一个boolean变量来判断当前状态是否重复。最后判断循环结束时的边界状态。
Time Complexity - O(n)， Space Complexity - O(1)。
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode dummy = new ListNode(-1);
ListNode node = dummy;
boolean isDuplicate = false;
while(head.next != null) {
if(head.next.val == head.val)
isDuplicate = true;
else {
if(!isDuplicate) {
node.next = head;
node = node.next;
} else
isDuplicate = false;
}
head = head.next;
}
if(isDuplicate)
node.next = null;
else
node.next = head;
return dummy.next;
}
}
二刷：
我发现自己的思路就是和自己的思路一样...磨蹭了半天，二刷还是写了跟一刷很类似的code....
我们主要就是用一个boolean hasDuplicate来记录之前是否出现过重复，以及一个dummy节点来保证假如链表头有重复我们也可以处理。
- 先做边界判断
- 建立fake head dummy， 以及 node = dummy
- 在head != null以及 head.next != null的条件下我们进行遍历
- 假如head.val == head.next.val， 我们判定hasDuplicate = true
- 否则head.val != head.next.val，这时候我们要进行分析
- 假如hasDuplicate =false，这时候我们这个head可以加入到结果之中去，我们执行node.next = head, node = node.next
- 否则我们不管
- 这时候重置hasDuplicate = false
- 每次head = head.next
- 最后判断最后一个元素，hasDuplicate为真时，我们把node.next设置为null,跳过最后一个重复元素， 否则node.next = head，返回结果
Java:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
ListNode node = dummy;
boolean hasDuplicate = false;
while (head != null && head.next != null) {
if (head.val == head.next.val) {
hasDuplicate = true;
} else {
if (!hasDuplicate) {
node.next = head;
node = node.next;
}
hasDuplicate = false;
}
head = head.next;
}
node.next = hasDuplicate ? null : head;
return dummy.next;
}
}
三刷:
思路跟上面都差不多
Java:
Time Complexity - O(n)， Space Complexity - O(1)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode node = dummy;
int count = 1;
while (head != null && head.next != null) {
if (head.val != head.next.val) {
if (count == 1) {
node.next = head;
node = node.next;
}
count = 1;
} else {
count++;
}
head = head.next;
}
node.next = (count == 1) ? head : null;
return dummy.next;
}
}