[数据结构与算法]leetcode83.删除排序链表中的重复元素

一.题目描述

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

二.题目解析

public ListNode deleteDuplicates2(ListNode head) {
        /*一趟遍历法，时间O(n),空间O(1)
        单指针法-删除相等的元素
        * */
        if(head == null || head.next == null){
            return head;
        }
        //由于重复元素只留一个head一定是不变的，所以无需引入dummyHead
        ListNode cur = head,after,newAfter;
        //由于是判断下一个节点的值是否与当前节点重复，所以终止条件是到达最后一个节点
        while (cur.next != null){
            after = cur.next;
            //如果值相等则当前元素指向下下个节点，且cur指针不变
            if(after.val == cur.val){
                newAfter = after.next;
                cur.next = newAfter;
                after.next = null;
            }else {
                //如果值不相等则cur指针后移
                cur = cur.next;
            }
        }
        return head;
    }

2.

public ListNode deleteDuplicates1(ListNode head) {
        /*更优雅的代码，时间O(n),空间O(1)
        双指针法-跳过相等的元素
        * */
        if(head == null || head.next == null){
            return head;
        }
        //dummy值能保证不会和链表所有节点值重复
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        //tail 代表当前有效链表的结尾
        ListNode tail = dummy;
        //head一直往后遍历
        while (head != null) {
            // 值不相等才追加，确保了相同的节点只有第一个会被添加到答案
            if (tail.val != head.val) {
                tail.next = head;
                tail = tail.next;
            }
            head = head.next;
        }
        tail.next = null;
        return dummy.next;
    }

3.

public ListNode deleteDuplicates(ListNode head) {
        /*递归，时间复杂度：O(N)，每个节点访问了一次。
            空间复杂度：O(N)，递归调用的时候会用到了系统的栈。
        * */
        //特殊条件判断&递归终止条件
        if(head == null || head.next == null){
            return head;
        }
        //如果当前元素的值和下个元素的值不相等
        if(head.next.val != head.val){
            //递归删除以下个元素为头结点的链表中的重复元素
            head.next = deleteDuplicates(head.next);
            //当前头结点保留，并返回即可
            return head;
        }else {
            //如果相等的话直接删除“当前头结点”，直接从head.next节点开始考虑即可
            return deleteDuplicates(head.next);
        }
    }