83. Remove Duplicates from Sorted List

83. Remove Duplicates from Sorted List:题目链接

方法1

// 时间复杂度O(N)  空间复杂度O(1)
struct ListNode *deleteDuplicates(struct ListNode *head) {
    if (head == NULL) {
        return NULL;
    }
    LinkNode *curNode = head;                         // 当前所在点
    LinkNode *nextNode = head->next;                  // 当前节点的下一个节点
    while (curNode && nextNode){
        if (curNode->val == nextNode->val){           // 两者数据域相等
            curNode->next = nextNode->next;
            nextNode = nextNode->next;
        } else{
            curNode = nextNode;
            nextNode = nextNode->next;
        }
    }
    return head;
}

方法2：双指针

与方法1相比慢一点

// 时间复杂度O(N)  空间复杂度O(1)   双指针
struct ListNode *deleteDuplicates(struct ListNode *head) {
    struct ListNode *dummy = (struct ListNode *) malloc(sizeof(struct ListNode));
    dummy->next = head;
    // fast : 最后一个重复元素的最后一个元素
    // slow : 链接重复元素之前的元素
    struct ListNode *fast = head, *slow = dummy;
    while (fast){
        while (fast->next != NULL && fast->next->val == fast->val) {
            fast = fast->next;
        }
        if (slow->next != fast) {
            slow->next = fast;
            slow = fast;
        }else{
            slow = slow->next;
        }
        fast = fast->next;
    }
    return dummy->next;
}

pS: 源代码链接