FXTi's blog
0%

remove-duplicates-from-sorted-list

Posted on Edited on

Remove Duplicates from Sorted List – LeetCode 83

Problem

Description

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Answer

Original

Code

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
		ListNode *curr = head;
		ListNode *last = head;
		while(curr){
			if(last->val != curr->val){
				if(last->next->val == last->val){
					last->next = curr;
					last = curr;
					curr = curr->next;
				} else {
					last = last->next;
					curr = curr->next;
				}
			}
			else
				curr = curr->next;
		}
		//There are duplicates at the end, so last locates before the last node,
		//and its next is not nullptr...
		if(last && last->next) last->next = nullptr;
        return head;
    }
};

思路

通过保持last作为当前已知有效节点的持有指针，然后用curr进行链表遍历的方法，思想类似于双指针，胜在内存访问较少，但依旧比较复杂，时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$9$ ms，排名$41.93\%$

Better

思路

同样是一次扫描，这个方法一旦后续节点的val重复就将其抛弃，及其简洁，但会产生一定的内存写回，尤其在链表的元素全部通过指针操作的情况下。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$13$ ms，排名$79.48\%$

Code

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