Remove Duplicates from Sorted List

• Easy
• tag: recursion
• 类似: reverse list, 所有list 的 recursion

Given a sorted linked list, delete all duplicates such that each element appear only once.

idea 1

• 这是我的写法. 很简单的思路, 因为有可能修改头结点. 例如: 1-1-1-1-1, val = 1. 此时返回[].
• 所以使用dummy node.
• 因为要删除节点, 所以必须知道prev node. 所以也使用一个global var: prev.
• algs很简单: 如果当前node的值等于val, 那么prev就跳过当前node. 否则prev update为当前node.
• 代码如下:

public ListNode removeElementsTTT(ListNode head, int val) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;
    while (head != null) {
      if (head.val == val) {
        pre.next = head.next;
      }
      else {
        pre = head;
      }
      head = head.next;
    }
    return dummy.next;
  }

idea 2

• 凡是list, tree, graph这种本身就是recursion build的数据结构肯定是有recursion解法的. 当然这题也不例外.
• recursion处理list, 特别是singly list的优势在于recursion的stack自动相当于保存了prev节点.
• 所以这里也是很优美的递归写法, 代码如下: 参考的discuss: 3 line recursion

public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
      return null;
    }
    head.next = removeElements(head.next, val);
    return head.val == val ? head.next : head;
  }