题解 | #删除有序链表中重复的元素-I#遍历

解法1:遍历

挨个遍历，同时保存上一个节点的值，如果当前节点的值等于上一个节点的值就删除，否则就继续遍历

import java.util.*;
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode current = head;
        while (current != null && current.next != null) {
            if (current.val != current.next.val) {
                current = current.next;
            } else {
                current.next = current.next.next;
            }
        }
        return head;
    }
}

解法2:递归

时间复杂度O(n)

空间复杂度是O(n)：因为需要一个栈保存临时的变量next

import java.util.*;

public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = deleteDuplicates(head.next);
        if(head.val == head.next.val) {
            head.next = head.next.next;
        }
        return head;
    }
}