Remove Duplicates from Sorted List II
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.
与Remove Duplicates from Sorted List相比,这道题目要求删除所有重复的元素,这样头结点可能会被删除,我们这时同样需要创建一个辅助节点,但是这次不是直接用辅助节点helper记录头结点,而是将helper.next = head,因为head可能会被删除,因此我们要返回的节点要根据helper.next来确定。这样相当于在原有链表的头上多加了一个节点,让head = helper,从head的开始操作,比较head.next的值与head.next.next的值,如果相等,用一个while循环来删除所有重复的元素;如果不等让head后移。最后返回helper.next。代码如下:
/**
* 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) return head;
ListNode helper = new ListNode(0);
helper.next = head;
head = helper;
while(head != null && head.next != null && head.next.next != null) {
if(head.next.val == head.next.next.val) {
int value = head.next.val;
while(head.next != null && head.next.val == value) {
head.next = head.next.next;
}
} else {
head = head.next;
}
}
return helper.next;
}
}