共计 2979 个字符,预计需要花费 8 分钟才能阅读完成。
题目形容
这是「牛客网」上的 「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」中比拟经典而又不过时的题目都讲一遍。
在提供谋求「证实」&「思路」的同时,提供最为简洁的代码。
欢送关注,交个敌人 (`・ ω ・´)
正文完