83. 删除排序链表中的重复元素
2020-08-29 本文已影响0人
一角钱技术
83. 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
方法1：遍历
算法思路：
这是一个简单的问题，仅测试你操作链表的结点指针的能力。由于输入的链表已排序，因此我们可以通过将结点的值与它之后的结点的值进行比较确定它是否为重复结点。如果它重复，我们更改当前结点的 next 指针，以便它跳过以下一个结点，并指向下下个结点。
参考代码1：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode curr = head;
while (curr != null && curr.next != null) {
if (curr.val == curr.next.val) {
curr.next = curr.next.next;
} else {
curr = curr.next;
}
}
return head;
}
}
复杂度分析：
- 时间复杂度：O(n)，n 是链表中结点数，因为链表中每个结点都检查一次以确定是否重复。
- 空间复杂度：O(1)，没有使用额外的空间。
方法1：递归
算法思路：
- 找终止条件：当
head指向链表只剩一个元素的时候，自然是不可重复的，因此return； - 想想应该返回什么值：应该返回的自然是已经去重的链表的头结点
- 递归每一步做什么：宏观上考虑，此时
head.next已经指向一个去重的链表，而根据第二步，我应该返回一个去重的链表的头节点。因此这一步应该做的是判断当前的head和head.next是否相等，如果相等则说明重复来，返回head.next，否则返回head。
参考代码2:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
head.next = deleteDuplicates(head.next);
if (head.val == head.next.val) {
head = head.next;
}
return head;
}
}
复杂度分析：
- 时间复杂度：O(n)，n 是链表中结点数，因为链表中每个结点都检查一次以确定是否重复。
- 空间复杂度：O(n)，递归过程使用的栈空间。
以上谢谢大家，求赞求赞求赞！
