题目描述
下面是给定的一段代码
/*** 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) {}
}
题目分析
这道题目的需求比较清晰，就是去重 ，而set集合中的元素具有唯一性，即set集合中不允许有重复的元素，每个元素在集合中只能出现一次。那么就想到如果将给定的元素全部存入到set集合中就可以实现去重的目的，最后输出set集合就行了。
但是但是，仔细阅读题目发现，方法中传入参数的数据是一个链表的头节点，而要求返回的是一个已排序的链表而不可以是集合。那么在我们接收数据的时候就要注意我们接收到的是一个链表的头节点，这样的话在向set集合中添加数据的时候就应该添加节点的value值，随后调用该节点的next指向下一个节点。这样就完成了向set集合中添加数据的一步。接下来就是返回结果了。目前，我们去重之后的数据存在set集合中，而题目要求返回的是一个已排序的链表，那么下面要做的就是将set集合中的数据存到链表中。给定的代码中已经给出了链表的定义，那么接下来像链表中存数据即可。
第一代代码
下面是按照分析的思路写出来的代码
/*** 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) {Set<Integer> set = new LinkedHashSet<>();ListNode newHead = head;while(newHead != null){set.add(newHead.val);newHead = newHead.next;}ListNode virtual = new ListNode(0);ListNode node = virtual;for(int value : set){node.next = new ListNode(value);node = node.next;}return virtual.next;}
}下面逐句分析一下这段代码：
Set<Integer> set = new LinkedHashSet<>();这一步是创建一个set集合，用于将数据实现去重操作后存到集合中。
ListNode newHead = head;定义一个指针newHead，初始时指向链表的头节点head，用于遍历整个链表
while(newHead != null){set.add(newHead.val);newHead = newHead.next;}这段代码开始遍历整个链表，直到newHead为空为止，接下来向set集合中添加当前节点的值val
下面将节点newHead移动到下一节点，继续遍历链表
ListNode virtual = new ListNode(0);这句话是创建一个虚拟头节点virtual，值为0，方便构造新的链表，最后返回链表时，只需要返回virtual.next即可
ListNode node = virtual;定义一个指针node用于构建新的链表，初始时指向虚拟头节点virtual
for(int value : set){node.next = new ListNode(value);node = node.next;}下面开始遍历set，构造去重后的链表，首先创建一个新节点，值为当前遍历的value，将新节点连接到node.next，相当于将新节点挂到链表末尾。再将node指针移动到刚刚创建的新节点，准备连接下一个节点。在遍历完set之后，循环结束。
return virtual.next;最后返回新链表的头节点即可。
这段代码虽然测试通过了，但是它的执行用时和消耗分布非常大，既然使用set集合时间空间都造成浪费的话，不如就在链表本身上进行操作
第二代代码
这段代码的时间复杂度为O(n),空间复杂度为O(1)
由于给定链表中的数据是有序的，那么只需要判断一下如果两个节点的值相等的话将一个节点删除就可以了。
/*** 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) {ListNode list = head;if(head == null){return head;}while(list.next!=null){if(list.val==list.next.val){list.next = list.next.next;}else{list = list.next;}}return head;}
}这是优化后的代码，下面将逐句的解释一下这段代码
ListNode list = head;定义变量list，初始化为链表头节点head
if(head == null){return head;}检查链表是否为空，如果为空，直接返回空链表，如果不为空则继续向下执行
while(list.next!=null){if(list.val==list.next.val){list.next = list.next.next;}else{list = list.next;}}开始遍历链表，如果当前节点的next不为空，表示链表还没有到达最后一个节点，下面进行条件判断，如果当前节点的值value和下一个节点的值value相等的话，就将当前节点指向当前节点的下一个节点的下一个节点，这样就将中间value重复的节点删除了。如果没有重复的节点就将list指针移动到下一节点，继续遍历。
最后将去重后的链表头节点head返回即可。
