【链表】LeetCode #83 删除排序链表中的重复元素 （两种方法）

题目链接：

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

题目描述：

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

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

通过次数123,788 提交次数242,480

方法一：

直接对比当前结点的值 cur.val 与下一个结点的值 cur.next.val 是否相等，若相等，则删掉，即 cur.next = cur.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;
    }
}

方法二：

当链表中重复元素超级无敌多时，每次遇到重复的都删除的话，需要做很多次链表删除操作，可以找到下一个比当前元素大的，直接让当前元素指向第一个比它大的元素，如果最后多位是重复的数字，即从链表的某一位开始到链表结束，都没有找到比当前位大的元素，则让 pre.next = null。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 /*
 * 设置指针 pre，初始指向链表的第一个元素
 * 当遇到比 pre 大的元素，pre.next = 该元素
 * 更新 pre = pre.next
 * 如果到链表尾都 == pre.val
 * 后面都不要，pre.next = null
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return head;
        ListNode cur = head;
        ListNode pre = head;
        while(cur != null){
            if(cur.val > pre.val){
                pre.next = cur;
                pre = cur;
            }else if(cur.next == null){//说明链表的最后几位是相同的数
                 pre.next = null;
            }
            cur = cur.next;
        }
        return head;
    }
}

其实链表的删除操作的时间复杂度为 O(n)，用方法一也不慢，只是提供两种思路，尤其是在重新接触链表题的时候，多绕绕多画图，思路也容易更清晰。