【算法】删除链表中重复元素-第一种:单指针

时间:2024-04-16 14:13:21

解题思路:

(1)声明一个指针指向头结点,比较cur指向的data域与cur->next指向的data域是否相等。

(2)如果相等,则删除该结点。

 (3)如果不相等,移动cur指针,继续比较。

 代码如下:

struct ListNode* deleteDuplicates(struct ListNode* head)
{
    struct ListNode     *cur,*tmp;
    cur = head;

    if( !head )
    {
        return NULL;
    }
    while( cur->next )
    {
        if( cur->val == cur->next->val )
        {
            tmp = cur->next;
            cur->next = cur->next->next;
            free(tmp);
        }
        else
        {
            cur = cur->next;
        }
    }
    return head;
}

复杂度分析

        时间复杂度:O(n)

        空间复杂度:O(1)