一、需求

给定一个已排序的链表的头 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指向链表的头结点，表示当前考察的结点。

首先，看下cur指向的结点和其后一个结点的值是否相等，如果相等则表示其后一个结点需要删除。

具体方法是将cur指向的结点的后继指针，指向其下一个结点的下一个结点。这样就将重复结点删除了

如下图，就是去除重复结点1之后，链表的结构。

这时cur所指向的结点的下一个结点的值是2，与cur所指向的结点值不同。

因此，不需要去重，这时将cur指向下一个结点，继续考察。这时，cur所指向的结点之后，没有其它结点，因此去重结束。

三、代码

创建链表类

ListNode.java

import cn.hutool.core.util.StrUtil;/*** 链表类** @author 王子威* @date 2021/4/21*/
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; }@Overridepublic String toString(){ListNode ln = this;StringBuilder sb = new StringBuilder();while(ln != null){if (StrUtil.isEmpty(sb)){sb.append("[" + ln.val);}else{sb.append("," + ln.val);}ln = ln.next;}sb.append("]");return sb.toString();}
}

测试接口

/*** 入口*      83. 删除排序链表中的重复元素*      1.创建升序链表* 输入：*      ListNode head = 1 -> 1 -> 2;* 输出：*      a.toString() = [1,2]* 解释：*      因为升序所以遇到下一个不同的值就是链接的地点*      我这里并未优化成上面概念*      这里的算法是：如果相同直接链接到下个节点，不然就直接复制临时值到下个节点*/
@Test
public void suanfa17()
{// 创建升序链表ListNode head = new ListNode(1);head.next = new ListNode(1);head.next.next = new ListNode(2);// 调用方法ListNode a = this.deleteDuplicates(head);// 这里重写了toStringSystem.out.println("a.toString() = " + a.toString());
}

调用方法：删除排序链表中的重复元素（链表去重）

/*** 删除排序链表中的重复元素（链表去重）** @param head* @return*/
public ListNode deleteDuplicates(ListNode head) {// 如果链表为空就直接返回nullif (head == null ) return null;// 不为空，复制头结点到临时节点ListNode temp = head;// 如果下一个节点不为空while(temp.next != null){// 临时节点值 = 下个节点的值if(temp.val == temp.next.val){// 将临时节点的链接到下下个节点上temp.next = temp.next.next;}else{// 否则将下个节点的值赋值给临时节点（因为节点不同）temp = temp.next;}}// 返回头节点return head;
}

作者：王子威

四、总结

• 学习了删除排序链表中的重复元素（链表去重）算法
• 测试用例废了点功夫，看来需要学习的还有很多
• 创建链接方案
• 获取链表的值
• 链表只要返回头结点，我们就可以根据头结点的地址获取下个节点了
• 算法兴趣+1 总:17
• 加强了对算法的分析能力