
题目描述
83. 删除排序链表中的重复元素
给定一个已排序的链表的头 head
, 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
示例 1:

1 2
| 输入:head = [1,1,2] 输出:[1,2]
|
示例 2:

1 2
| 输入:head = [1,1,2,3,3] 输出:[1,2,3]
|
提示:
- 链表中节点数目在范围
[0, 300]
内
-100 <= Node.val <= 100
- 题目数据保证链表已经按升序 排列
解题思路
方法:递归
使用递归实现,若当前节点值等于下一节点值,则设置当前节点的下一节点为下下个节点
注意:
- 需要考虑连续 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 {
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; } } }
|