82.删除排序链表中的重复元素Ⅱ
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
题解：
本题要求是在一个有序链表中，把重复的节点都删除，由于是有序的，因此重复的节点都是相邻的。可以使用递归和迭代两种方法去解决。下面分别介绍这两种方法，正常链表题好像都是有这两种方法。
- 递归法：
首先，我们需要明确三个点，递归函数的作用是什么，递归函数的出口是什么，我们能解决什么小问题，然后将后续的逻辑交给递归函数。写递归逻辑的时候，在函数中调用递归函数本身的时候，将他当成已经实现的函数来使用。
ListNode deleteDuplicates(ListNode head)的作用是，将从head节点开始，将后面所有重复的节点都删除，并返回头节点- 递归函数的出口：那必然是当head为空，或者head的下一个是空（链表只有一个节点，必不可能重复）。直接返回头节点
- 我们能解决的小问题：我们只需要解决第一个head及其后面连续节点的删除工作即可。这里会涉及到两种情况。
- head和它后面的节点不重复：这种情况，我们就不需要删除任何节点，直接将head.next交给递归函数处理即可
- head和它后面的节点重复：这种情况，我们需要删除head为首的及其后续所有值等于head的节点，随后找到第一个不重复的节点，以这个节点作为链表头交给递归函数进行处理。
看如下案例：
对于链表1 -> 2 -> 2 -> 2 -> 3 -> 4的重复节点删除
上述案例在2节点的时候，将三个连续的2节点删除，然后再将后续节点送入到deleteDuplicates中继续删除，将这个结果，作为上一层deleteDuplicates的结果返回给head的next。
代码实现如下：
package com.offer;
import com.offer.leetcode.datastruct.ListNode;
import com.offer.leetcode.datastruct.ListNodeUtils;
import java.util.List;
public class _82删除排序链表中的重复元素Ⅱ {
public static void main(String[] args) {
int[] arr = new int[]{1, 1, 1, 1, 2, 3, 4, 5, 6, 6, 6, 6, 7, 8, 9, 10, 10, 10};
ListNode list = ListNodeUtils.createList(arr);
ListNodeUtils.printListNode(list);
ListNode header = deleteDuplicates(list);
ListNodeUtils.printListNode(header);
}
public static ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 只处理链表的头，剩下的交给递归
if (head.val != head.next.val) {
// 因为没有重复，所以不删除头节点
head.next = deleteDuplicates(head.next);
return head;
}else {
// 头节点出现重复了，找到不同的
ListNode noDup = head.next;
while (noDup != null && noDup.val == head.val) {
noDup = noDup.next;
}
return deleteDuplicates(noDup);
}
}
}
- 迭代法：
迭代法同理，这里需要了解的一个小技巧是，因为在这道题中head是会发生变化的，因此可以创建一个dummy节点，让它的下一个指向head节点，最后返回dummy的下一个即可，这样即使后续的head被删了，我们最后返回的头节点的写法还是不会变化的。
代码实现如下：
package com.offer;
import com.offer.leetcode.datastruct.ListNode;
import com.offer.leetcode.datastruct.ListNodeUtils;
import java.util.List;
public class _82删除排序链表中的重复元素Ⅱ {
public static void main(String[] args) {
int[] arr = new int[]{1, 1, 1, 1, 2, 3, 4, 5, 6, 6, 6, 6, 7, 8, 9, 10, 10, 10};
ListNode list = ListNodeUtils.createList(arr);
ListNodeUtils.printListNode(list);
ListNode header = deleteDuplicates(list);
ListNodeUtils.printListNode(header);
}
/**
* 迭代法求解
* @param head 头节点
* @return
*/
public static ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 因为在这个题里面头节点可能会发生变动，因此需要重新创建出一个虚拟的头节点
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode noDup = head;
while (noDup != null) {
// 跳到下一个不重复的，
while (noDup.next != null && noDup.val == noDup.next.val) {
noDup = noDup.next;
}
if (pre.next == noDup) {
// 进入到这里说明没有重复节点
pre = pre.next;
}else {
// 如果有重复节点
pre.next = noDup.next;
}
noDup = noDup.next;
}
return dummy.next;
}
}
