83. Remove Duplicates from Sorted List

1.問題

• 如果linked list中的元素出現超過一次, 則list只讓該元素出現一次

2.想法

• 提問:

• function header, parameter

• test input

• 說明想法

  • 一邊移動一邊移除node:

    • Create一個dummy node, 初始狀態下*pre指向這個node, newNode->next = head, 這樣無論是要移除哪個node等同於從list中間移除node

    • pre->next = curr->next

    • curr->next = NULL

    • pre = pre->next

• 測試計算複雜度

3.程式碼

/**
 * 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* tmp = new ListNode(0);
        ListNode* curr = head;
        ListNode* pre = tmp;
        pre->next = curr;
        while (curr && curr->next) {
            if (curr->val == curr->next->val) {
                pre->next = curr->next;
                curr->next = NULL;
                curr = pre->next;
            } else {
                pre = curr;
                curr = curr->next;
            }
        }
        
        return tmp->next;
    }
};