83. 删除排序链表中的重复元素

83. 删除排序链表中的重复元素

一次循环遍历解法：

时间复杂度：O(n)
空间复杂度：O(1)

    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            if (null == head) {
                return head;
            }
            // - 初始化一个当前节点的指针
            ListNode currentNode = head;
            while (null != currentNode.next){
                // - 如果当前节点和下一个节点相同
                if(currentNode.next.val == currentNode.val){
                    // - 下一个节点 = 下一个节点的下一个节点 == 删除节点
                    currentNode.next = currentNode.next.next;
                } else {
                    currentNode = currentNode.next;
                }
            }
            // - 返回相同节点后的链表
            return head;
        }
    }

递归解法：

时间复杂度：O(n)
空间复杂度：O(n^2)

    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            if (null == head || null == head.next) {
                return head;
            }
            // - 递归处理
            head.next = deleteDuplicates(head);

            // - 关键代码： 如果相同则返回 下一个节点
            return head.val == head.next.val ? head.next : head;
        }
    }