记录题解快慢指针法。
利用快指针,过滤掉重复的节点;使用慢指针构造出没有重复节点的新链表。
public class Solution { public ListNode deleteDuplication(ListNode pHead) { ListNode pre = new ListNode(0); ListNode cur = pre; while (pHead != null) { // 进入循环时,确保了 pHead 不会与上一节点相同 if (pHead.next == null || pHead.next.val != pHead.val) { cur.next = pHead; cur = pHead; } // 如果 pHead 与下一节点相同,跳过相同节点(到达「连续相同一段」的最后一位) while (pHead.next != null && pHead.val == pHead.next.val) pHead = pHead.next; pHead = pHead.next; } cur.next = null; // 对于末尾有重复的元素,while循环结束后将tail.next置为null,即将其后重复节点删除了 return pre.next; } }
看到别的题解,记录一下(递归方法)。
1.递归出口:考虑什么情况下,我们不再需要「删除」操作。显然当传入的参数 pHead 为空,或者 pHead.next 为空时,必然不存在重复元素,可直接返回 pHead;
2.递归环节的最小操作:之后再考虑删除逻辑该如何进行:
显然,当 pHead.val != pHead.next.val 时,pHead 是可以被保留的,因此我们只需要将 pHead.next 传入递归函数,并将返回值作为 pHead.next,然后返回 pHead 即可;
当 pHead.val == pHead.next.val 时,pHead 不能被保留,我们需要使用临时变量 tmp 跳过「与 pHead.val 值相同的连续一段」,将 tmp 传入递归函数所得的结果作为本次返回。
public class Solution { public ListNode deleteDuplication(ListNode pHead) { // 递归出口:当「输入节点为空」或者「不存在下一节点」,直接返回 if (pHead == null || pHead.next == null) return pHead; if (pHead.val != pHead.next.val) { // 若「当前节点」与「下一节点」值不同,则当前节点可以被保留 pHead.next = deleteDuplication(pHead.next); return pHead; } else { // 若「当前节点」与「下一节点」相同,需要跳过「值相同的连续一段」 ListNode tmp = pHead; while (tmp != null && tmp.val == pHead.val) tmp = tmp.next; return deleteDuplication(tmp); } } }