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

题目描述：

给定一个已排序的链表的头?head?，?删除所有重复的元素，使每个元素只出现一次?。返回?已排序的链表?。

题目解析(遍历)：

只需要遍历所有链表结点，当一个结点的值和该结点下一结点的值相同时，我们将该结点的next指向该结点的下下结点，若不相同的时候，我们将结点往后移继续接着判断，直到当前结点为链表最后一个结点，代码如下：

// 遍历-java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null)return head;
        ListNode cur = head;
        while(cur.next!=null){
            if(cur.val==cur.next.val){
                cur.next = cur.next.next;
            }
            else{
                cur = cur.next;
            }
        }
        return head;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：40.8 MB, 在所有 Java 提交中击败了90.92%的用户

// 遍历-cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==nullptr)return head;
        ListNode* cur = head;
        while(cur->next!=nullptr){
            if(cur->val==cur->next->val)cur->next = cur->next->next;
            else cur = cur->next;
        }
        return head;
    }
};

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：40.8 MB, 在所有 Java 提交中击败了90.92%的用户

题目解析(递归)：

我们发现随着我们将结点的next指针改变了，整个链表会随着缩短，但操作的方式是一样的，我们从后往前进行判断，如果两个连续结点的值相同，我们返回后一个结点，若不相同我们返回前一个结点，代码如下：

// 递归-java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null)return head;
        head.next = deleteDuplicates(head.next);
        return head.val==head.next.val?head.next:head;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：40.8 MB, 在所有 Java 提交中击败了88.94%的用户

// 递归-cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==nullptr||head->next==nullptr)return head;
        head->next = deleteDuplicates(head->next);
        return head->val==head->next->val?head->next:head;
    }
};

执行用时：8 ms, 在所有 C++?提交中击败了83.31%的用户

内存消耗：11.3 MB, 在所有 C++?提交中击败了34.39%的用户