链表的操作非常常见，也是面试中经常会被问道的问题。对于链表重复元素的删除，有两个变体，现在总结如下。
链表代码如下：
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
1.删除重复元素，所有元素只保留一次。
* @description 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
* 示例 1:
* 输入: 1->1->2
* 输出: 1->2
* 示例 2:
* 输入: 1->1->2->3->3
* 输出: 1->2->3
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
这个问题的解法非常简单，只需要定义一个指针然后while循环即可。
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (null!=cur&&null!=cur.next){
if(cur.val == cur.next.val){
if(null != cur.next.next){
cur.next = cur.next.next;
}else {
cur.next = null;
}
}else {
cur = cur.next;
}
}
return head;
}
定义一个指针cur，然后循环判断cur.value和cur.next.value，如果相等，那么就将后面重复元素移除。如果不等，则指针后移。
2.删除全部重复的元素，只保留没有重复的元素。
*@description
* 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
* 示例 1:
* 输入: 1->2->3->3->4->4->5
* 输出: 1->2->5
* 示例 2:
* 输入: 1->1->1->2->3
* 输出: 2->3
* 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
本文需要重点关注的是这个变体，因为问题1的解法很简单。没什么特别的。但是加上了将全部重复的数字都去除这个条件之后，难度瞬间增加了不少。你需要考虑两个问题：
- 如果链表头就是重复的数字怎么办
- 如何移动比较链表，删除元素？
第一，对于表头重复的问题，那么最简单的办法就是在表头添加一个元素，加入链表。之后在链表遍历完之后，返回哨兵的next。这是一个非常好的办法，简直是以后解决链表类问题的套路之一。
ListNode cur = new ListNode(0);
cur.next = head;
head = cur;
仅仅三行代码就搞定了。
第二，对于如何移动比较的问题，此时发现，用一个指针无论如何也无法实现题目的需求了。此时看到了参考文档中的三指针法。现在将文章中的内容发下来：
除了哨兵之外，需要定义一个left和一个right两个指针。
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
先用right和right下一个元素比较，如果相等，则left移动。之后循环判断left和right两个指针是否指向同一个元素。如果相等，则说明没有相同的元素。哨兵cur向后移动。反之，则说明存在相同的元素，哨兵则将当前next指针指向right.next,将重复元素都删除。完整算法如下：
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = new ListNode(0);
cur.next = head;
head = cur;
ListNode left,right;
while (null!=cur&&null!=cur.next){
left = cur.next;
right = cur.next;
while (null!=right.next&&right.next.val==left.val){
right = right.next;
}
if(right == left){
cur = cur.next;
}else {
cur.next = right.next;
}
}
return head.next;
}
三指针法，也是一个经典的算法。在后续面链表相关问题的时候，又是一个新套路。
网友评论