题解 | JAVA #删除有序链表中重复的元素-II# [P3]

sentinal指向之前遍历过的所有unique元素组成的链表。
lastUnique指向该链表的最后一个元素

遍历时每发现一个unique元素(与相邻元素值不想等)，将其append到lastUnique的后面就完事儿了。

时间 O(n)
空间 O(1)

import java.util.*;

public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
      if (head == null) return null;
      
      ListNode sentinal = new ListNode(-1);
      ListNode lastUnique = sentinal;
      ListNode n = head;
      int lastVal = -1;
      
      while (n != null) {
        if (n.val != lastVal && (n.next == null || n.val != n.next.val)) {
          lastUnique.next = n;
          lastUnique = n;
        } 
        lastVal = n.val;
        n = n.next;
      }
      
      // 这一步不能漏, 不然链表尾端的重复元素还连在lastUnique后面
      lastUnique.next = null;
      return sentinal.next;
    }
}