关于java:剑指-の-精选详解删除链表中重复结点的两种解法

这是「牛客网」上的 「JZ 56 删除链表中反复的结点」，难度为 「较难」。

Tag :「剑指 Offer」、「链表」、「单链表」

在一个排序的链表中，存在反复的结点，请删除该链表中反复的结点，反复的结点不保留，返回链表头指针。

例如，链表 1->2->3->3->4->4->5 解决后为 1->2->5

示例 1：

 输出：{1,2,3,3,4,4,5}

返回值：{1,2,5}

要求：

工夫：1 s
空间：64 M

首先一个比拟「直观且通用」的思路是，采纳「边遍历边结构」的形式：

建一个「虚构头节点」dummy 以缩小边界判断，往后的答案链表会接在 dummy 前面；
应用 tail 代表以后无效链表的结尾；
通过原输出的 pHead 指针进行链表扫描。

对原链表进行遍历，只有原链表尚未达到结尾，咱们就反复如下决策（保留 / 跳过逻辑）：

保留：pHead 曾经没有下一个节点，pHead 能够被保留（插入到答案结尾指针 tail 前面）；pHead 有一下个节点，然而值与 pHead 不雷同，pHead 能够被保留；
跳过：当发现 pHead 与下一个节点值雷同，须要对「间断雷同一段」进行跳过。

举个 🌰，以题目示例 [1,2,3,3,4,4,5] 为例，应用图解的形式来感受一下。

「以后节点」与「下一节点」值不同，以后节点进行保留：

「以后节点」与「下一节点」值雷同，跳过「雷同的间断一段」，以后节点不能保留：

代码：

class Solution {public ListNode deleteDuplication(ListNode pHead) {ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        while (pHead != null) {
            // 进入循环时，确保了 pHead 不会与上一节点雷同
            if (pHead.next == null || pHead.next.val != pHead.val) {
                tail.next = pHead;
                tail = pHead;
            }
            // 如果 pHead 与下一节点雷同，跳过雷同节点（达到「间断雷同一段」的最初一位）while (pHead.next != null && pHead.val == pHead.next.val) pHead = pHead.next;
            pHead = pHead.next;
        }
        tail.next = null;
        return dummy.next;
    }
}

工夫复杂度：
空间复杂度：

递归解法相比于迭代解法，代码要简洁一些，但思维难度要高一些。

首先无论是否为“链表”类的题目，在实现递归前，都须要先明确「咱们冀望递归函数实现什么性能」，即设计好咱们的递归函数签名。

显然，咱们心愿存在一个递归函数：传入链表头结点，对传入链表的反复元素进行删除，返回操作后的链表头结点。

该性能与题目要咱们实现的 deleteDuplication 函数雷同，因而咱们间接应用原函数作为递归函数即可。

之后再思考「递归进口」和「递归环节的最小操作」：

递归进口：思考什么状况下，咱们不再须要「删除」操作。显然当传入的参数 pHead 为空，或者 pHead.next 为空时，必然不存在反复元素，可间接返回 pHead；
递归环节的最小操作：之后再思考删除逻辑该如何进行：
显然，当 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);
        }
    }
}

工夫复杂度：
空间复杂度：疏忽递归带来的额定空间开销，复杂度为

如果问题变为「雷同节点保留一个」，该如何实现？

实质没有扭转，只须要抓住「遍历过程中，节点何时可能被保留」即可。

代码：

class Solution {public ListNode deleteDuplication(ListNode head) {if (head == null) return head;
        ListNode dummy = new ListNode(-109);
        ListNode tail = dummy;
        while (head != null) {
            // 值不相等才追加，确保了雷同的节点只有第一个会被增加到答案
            if (tail.val != head.val) {
                tail.next = head;
                tail = tail.next;
            }
            head = head.next;
        }
        tail.next = null;
        return dummy.next;
    }   
}

工夫复杂度：
空间复杂度：

这是咱们「剑指の精选」系列文章的第 No.56 篇，系列开始于 2021/07/01。

该系列会将「剑指 Offer」中比拟经典而又不过时的题目都讲一遍。

在提供谋求「证实」&「思路」的同时，提供最为简洁的代码。

欢送关注，交个敌人 (`・ ω ・´)

关于java:剑指-の-精选详解删除链表中重复结点的两种解法

题目形容

迭代解法

递归解法

拓展

最初