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

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

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

初步分析

这个题会链表的话感觉就很简单没什么复杂的过程，如下图所示。当我们当前指针的指向的值2和后边的2是一样的时候，直接将当前指针下一个节点指向下下个数3，即直接丢弃中间这个重复的值2。那么下一次比较的时候，当前值2，如果和后边的数3不一样，则当前的值往后移动为3，如果一样，则重复上一次的操作。

继续分析

那么剩下来的就是怎么遍历链表的问题了。首先得回到首节点，必须引入一个新的链表，指向这个链表。那么就拿到之前链表的头节点，这时候如果他的next节点不为空，就继续遍历。

答案

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; }
}
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;
}

复杂度

• 时间复杂度: O(n),需要遍历一遍链表。
• 空间复杂度：O(1)。

总结

单链表是我们在数据结构中非常常见的链表，那么最简单的删除链表元素你会吗？什么so easy?那下一篇？你不会？我这里随便在网上找了篇文章，不会链表的可以去看看。图解！链表真的很简单。

这个题关键就是指针指向问题以及怎么寻找头指针以及怎么遍历链表。链表分为数据域和指针域，比较数据域，修改指针域。

删除链表的元素是链表的基本操作，我感觉这个题，可能是为后续的题做的铺垫，那么我们拭目以待吧。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！