每日一题-20240121

题目描述

83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表

示例 1:

img

1
2
输入:head = [1,1,2]
输出:[1,2]

示例 2:

img

1
2
输入:head = [1,1,2,3,3]
输出:[1,2,3]

提示:

  • 链表中节点数目在范围 [0, 300]
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序 排列

解题思路

方法:递归

使用递归实现,若当前节点值等于下一节点值,则设置当前节点的下一节点为下下个节点

注意:

  1. 需要考虑连续 2 个节点以上节点相同值的场景;
  2. 需要考虑“归”的条件;

代码实现

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution83 {
/**
* 思路:使用递归实现
* 若当前节点值等于下一节点值,则设置当前节点的下一节点为下下个节点
*
* @param head
* @return {@link ListNode }
* @author Forest Dong
* @date 2024/01/24 19:44
*/
public static ListNode deleteDuplicates(ListNode head) {
delete(head);
return head;
}

private static void delete(ListNode node) {
if (null == node || null == node.next) {
return;
}
if (node.val == node.next.val) {
if (null == node.next.next) {
node.next = null;
} else {
node.next = node.next.next;
// 这里需要继续递,防止连续多个重复元素
delete(node);
}
}
delete(node.next);
}

public static void main(String[] args) {
ListNode node5 = new ListNode(3);
ListNode node4 = new ListNode(3, node5);
ListNode node3 = new ListNode(2, node4);
ListNode node2 = new ListNode(1, node3);
ListNode node1 = new ListNode(1, node2);
ListNode listNode = deleteDuplicates(node1);
while (null != listNode) {
System.err.println(listNode.val);
listNode = listNode.next;
}
}
}

更优解

方法:一次遍历

思路与算法

由于给定的链表是排好序的,因此重复的元素在链表中出现的位置是连续的,因此我们只需要对链表进行一次遍历,就可以删除重复的元素。

具体地,我们从指针 cur 指向链表的头节点,随后开始对链表进行遍历。如果当前 cur与 cur.next 对应的元素相同,那么我们就将 cur.next 从链表中移除;否则说明链表中已经不存在其它与 cur 对应的元素相同的节点,因此可以将 cur 指向 cur.next。

当遍历完整个链表之后,我们返回链表的头节点即可。

细节

当我们遍历到链表的最后一个节点时,cur.next 为空节点,如果不加以判断,访问 cur.next 对应的元素会产生运行错误。因此我们只需要遍历到链表的最后一个节点,而不需要遍历完整个链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class BetterSolution83 {
public static ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode cur = head;
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}

public static void main(String[] args) {
ListNode node5 = new ListNode(3);
ListNode node4 = new ListNode(3, node5);
ListNode node3 = new ListNode(2, node4);
ListNode node2 = new ListNode(1, node3);
ListNode node1 = new ListNode(1, node2);
ListNode listNode = deleteDuplicates(node1);
while (null != listNode) {
System.err.println(listNode.val);
listNode = listNode.next;
}
}
}