存在一个按升序排列的链表,给你这个链表的头节点head,请你删除所有重复的元素,使每个元素只出现一次。 返回同样按升序排列的结果链表。 示例 1: 输入:head = [1,1,2] 输出:[1,2]
示例 2: 输入:head = [1,1,2,3,3] 输出:[1,2,3]
提示: 链表中节点数目在范围 [0, 300] 内 -100 <= Node.val <= 100 题目数据保证链表已经按升序排列
这题说了链表中的值是按照升序排列的,既然是排过序的,那么相同的节点肯定是挨着的。我们可以使用一个指针cur,每次都要判断是否和他后面的节点值相同,如果相同就把后面的那个节点给删除,这里就以示例2为例来看个视频
最后再来看下代码
public ListNode deleteDuplicates(ListNode head) { //如果但前节点是空,或者是单个节点,直接返回 if (head == null || head.next == null) return head; //只用一个指针cur指向当前节点 ListNode cur = head; while (cur.next != null) { //如果当前节点的值和下一个节点的值相同, //就把下一个节点值给删除 if (cur.val == cur.next.val) { cur.next = cur.next.next; } else { //否则cur就往后移一步 cur = cur.next; } } return head; }
除了上面使用一个指针以外,我们还可以使用递归的方式来解决。这个需要对链表的逆序访问比较熟悉,关于链表的逆序访问也可以看下1,倒叙打印链表。我们还以示例1为例来画个图看一下(如果看不清,图片可点击放大) 最后再来看下代码 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; }
|