Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 2->3
Solution
- 由于是sorted linked list，所以重复节点一定是排在一起的。
- 头结点有可能被删除，所以需要
dummy node。 -
current node从dummy node开始,next node是current.next：- 需要判断
next与next.next是否重复，如果重复继续寻找其后还有没有与之重复的节点，直到找不到为止， 且每一次next = next.next所在的节点。最后next停留的节点就是这一组重复节点的最后一个，然后连接current.next = next.next。 - 如果
next与next.next没有重复，current = current.next。
- 需要判断
重复上述1，2步骤，遍历完整个链表。
O(n) Time, O(1) Space
image.png
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode (0);
dummy.next = head;
ListNode current = dummy;
ListNode next = dummy.next;
while (current.next != null && current.next.next != null)
{
if (current.next.val != current.next.next.val)
{
current = current.next;
}
else {
next = current.next;
while (next.next != null && next.val == next.next.val)
{
next = next.next;
}
current.next = next.next;
}
}
return dummy.next;
}
}
