链表问题(算法题)

1、从已排序的链表中删除重复的单元。如:

输入:1->1->2,输出:1->2

如:

输入:1->1->2->2->3,输出 1->2->3

思路:

双指针;

快指针先往后移动,如果快指针的值不等于慢指针的值,就释放掉中间的指针空间,并且将慢指针next指向快指针,把快指针赋值给快指针。

Node* deleteDuplicationNodeFromSortedList(Node* &pHead)
{
    if (pHead == NULL || pHead->next == NULL)
    {
        return pHead;
    }

    Node* node_slow = pHead;
    Node* node_fast = pHead;

    while (node_fast != NULL)
    {
        if (node_fast->value != node_slow->value)
        {
            freeNodeBetweenTwoPointer(node_slow, node_fast);
            node_slow->next = node_fast;
            node_slow = node_fast;
        }

        node_fast = node_fast->next;
    }

    if (node_slow->next != node_slow)
    {
        node_slow->next = node_fast;
    }

    return pHead;
}

  

2、给定有序链表,删除出现三次以上的元素。如:

输入:1->1->2->3->3->3

返回:1->1->2

思路:双指针

如果快指针的值不等于慢指针的值,那么快慢指针就都往前走一步;如果遇到相同的数,快指针就继续往前走,同时计数,超过三次以后就接着走直到碰到新数字以后修改慢指针的next

//这个还是有点复杂的,我想了挺久的
//主要难点在于如果没有头结点的链表进来第一个结点值是大于3的怎么处理
//在慢指针的值不等于快指针的值的时候
Node* deleteDuplicationNodeThreeTimes(Node* &pHead)
{
    if (pHead == NULL || pHead->next == NULL)
    {
        return pHead;
    }

    Node* node_slow = pHead;
    Node* node_before = node_slow;
    Node* node_fast = pHead->next;


    while (node_fast != NULL)
    {
        int delete_cnt = 1;
        int delete_num = node_fast->value;

        while (node_fast->next != NULL && delete_num == node_fast->next->value)
        {
            delete_cnt++;
            node_fast = node_fast->next;
        }

        if (delete_cnt >= 3)
        {
            node_slow->next = node_fast->next;
        }
        else
        {
            node_slow = node_fast;
        }

        node_fast = node_fast->next;

    }

    return pHead;

}
Node* deleteDuplicationNodeThreeTimes(Node* &pHead)
{
    if (pHead == NULL || pHead->next == NULL)
    {
        return pHead;
    }

    Node* node_slow = pHead;
    Node* node_before = node_slow;
    Node* node_fast = pHead->next;


    while (node_fast != NULL)
    {
        int cnt = 0;
        while (node_fast != NULL && node_slow->next->value == node_fast->value)
        {
            cnt++;
            node_fast = node_fast->next;
        }

        if (cnt >= 3)
        {
            node_slow->next = node_fast;
        }
        else
        {
            while (node_slow->next != node_fast)
            {
                node_slow = node_slow->next;
            }
        }
    }

    return pHead;

}

3、给定无序链表,删除出现三次以上的元素。

思路:hash算法

两次遍历,第一次遍历统计元素出现的次数,第二次遍历查看对应的value值出现次数是否大于3,是就删除,否则就继续走。

//默认传进来的链表是带有头结点的
Node* deleteNodeThreeTimesFromUnordered(Node* &pHead)
{
    if (pHead == NULL || pHead->next == NULL )
    {
        return pHead;
    }

    unordered_map<int, int> hash_value;
    Node* node_tmp = pHead->next;

    while(node_tmp != NULL)
    {
        hash_value[ node_tmp->value ]++;
        node_tmp = node_tmp->next;
    }

    node_tmp = pHead;
    while (node_tmp->next != NULL)
    {
        if (hash_value[node_tmp->next->value] >= 3)
        {
            Node* node_free = node_tmp->next;
            node_tmp->next = node_free->next;
            free(node_free);
        }
        else
        {
            node_tmp = node_tmp->next;
        }
    }
    
    return pHead;
}

4、无序列表,要求出现次数不能超过本身的value值。

思路:hash

两次遍历。第一次遍历统计元素次数,第二次遍历查看出现次数是否超过value值,超过就删除,并且把对应的hash的value值减1.

Node* deleteNodeOverValueTimesFromUnordered(Node* &pHead)
{
    if (pHead == NULL || pHead->next == NULL)
    {
        return pHead;
    }

    unordered_map<int, int> hash_value;
    Node* node_tmp = pHead->next;

    while (node_tmp != NULL)
    {
        hash_value[ node_tmp->value ]++;
        node_tmp = node_tmp->next;
    }

    node_tmp = pHead;
    while (node_tmp->next != NULL)
    {
        if (node_tmp->next->value < hash_value[ node_tmp->next->value ] )
        {
            hash_value[ node_tmp->next->value ]--;
            Node* node_free = node_tmp->next;
            node_tmp->next = node_free->next;
            free(node_free);
        }
        else
        {
            node_tmp = node_tmp->next;
        }
    }

    return pHead;
}
原文地址:https://www.cnblogs.com/wanghao-boke/p/13887424.html