有序链表删除重复节点

有序链表删除重复节点

问题

这个题目说的是，给你一个单链表，这个单链表节点上的数字是有序的。对于出现多次的数字，你要把它们全删掉，留下只出现一次的节点，最后返回处理后的单链表。

比如说，给你的有序单链表是：

1 -> 1 -> 2 -> 4

1 出现了多次，删掉它后，你要返回的链表是：

2 -> 4

代码

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

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

  // Time: O(n), Space: O(1)
  public ListNode removeDuplicatesInSortedList(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy, cur = prev.next;
    while (cur != null) {
      while (cur.next != null && cur.val == cur.next.val) cur = cur.next;
      // update prev
      if (prev.next != cur) prev.next = cur.next;
      else prev = prev.next;
      // update cur
      cur = prev.next;
    }
    return dummy.next;
  }

}