WHCSRL 技术网

《中英双解》leetCode 83 Remove Duplicates from Sorted List(删除排序链表中的重复元素)

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除所有重复的元素,使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

Example 1:

Input: head = [1,1,2]
Output: [1,2]

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

这题不是很难,遍历一下就行,我这个代码有一个问题,就是循环里面不能省略else,不然会有空指针异常,不知道为啥。

  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. * int val;
  5. * ListNode next;
  6. * ListNode() {}
  7. * ListNode(int val) { this.val = val; }
  8. * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9. * }
  10. */
  11. class Solution {
  12. public ListNode deleteDuplicates(ListNode head) {
  13. if(head == null) return head;
  14. ListNode prev = head;
  15. while(prev.next != null){
  16. if(prev.val == prev.next.val){
  17. prev.next = prev.next.next;
  18. } else {
  19. prev = prev.next;
  20. }
  21. }
  22. return head;
  23. }
  24. }

 

复杂度分析

  • 时间复杂度:O(n)O(n),其中 nn 是链表的长度。

  • 空间复杂度:O(1)O(1)

推荐阅读