有序链表去重

有序链表去重

问题

这个题目说的是，给你一个单链表，这个单链表节点上的数字是有序的。对于出现多次的数字，你要把重复的去掉，只保留一个即可。最后返回去重后的单链表。

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

1 -> 1 -> 2 -> 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) {
    if (head == null) return null;
    ListNode cur = head, next = head.next;
    while (next != null) {
      if (cur.val == next.val)
        cur.next = next.next;
      else
        cur = cur.next;
      next = next.next;
    }
    return head;
  }

}