移除排序链表的重复节点

发表于 | 分类于 |
字数统计: 274 字 | 阅读时长 ≈ 1 分钟

题目描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1：
输入: 1->1->2
输出: 1->2

示例 2：
输入: 1->1->2->3->3
输出: 1->2->3

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public ListNode deleteDuplicates(ListNode head) {

  }
}

方法一：单指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
  public ListNode deleteDuplicates(ListNode head) {
    if(head == null) return null;
    ListNode cur = head;
    while(cur.next != null) {
      if(cur.val == cur.next.val) {
        cur.next = cur.next.next;
      } else {
        cur = cur.next;
      }
    }
    return head;
  }
}

复杂度分析：

  • 时间复杂度：O(n)，因为列表中的每个结点都检查一次以确定它是否重复，所以总运行时间为 O(n)，其中 n 是列表中的结点数

  • 空间复杂度：O(1)，没有使用额外的空间

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：39.6 MB, 在所有 Java 提交中击败了28.00%的用户