[数据结构与算法]面试必备好题【链表】【01】【LeetCode】【刷题】

前言🐱

hello，大家好啊，今天继续刷题，本次刷的是链表专题。

链表练习🐦

NO1.移除链表元素

不带哨兵位：

一定一定要考虑清楚多种情况再写代码。

注意不能一开始就动了head，因为要返回head，如果一开始就用head来操作，那后面就找不到链表的起点了。

此题是通过返回头结点来改变实参，因此不需要传二级指针。

要删除中间某一个，需要先找到其前一个，下一次就要让cur指向val的下一个。

1. 中间有几个val
2. 链表为空
3. 全是val
4. 第一个就是val，会出现prev-> next 空指针解引用的问题，而且如果直接free掉第一个节点的，链表的头也应该变。
   因此我们只需要直接干掉第一个节点，并让head指向下一个节点，然后再让cur 往后移动一位。

做题时，先处理正确情况，然后再针对特殊情况处理，有时候，某些特殊情况是能合并一起处理的，比如上面的全是val 和第一个是val的情况就可以合并处理了。空链表和普通情况也是能合并处理。

考虑到经常需要用到cur的下一个节点，因此我们最好提前保存起来。

完全照着画图的思路写的

struct ListNode *removeElements(struct ListNode *head, int val)
{
    struct ListNode *prev = NULL;
    struct ListNode *cur = head;
    while (cur) // cur不为空才进的来
    {
        struct ListNode *next = cur->next;
        //找到val之后让prev指向val的下一个，free掉cur，并让cur去到val的下一个
        if (cur->val == val)
        {
            //考虑第一个节点就是val的情况
            //直接干掉第一个节点，并让head指向下一个节点，然后再让cur往后移动一位。
            if (prev == NULL)
            {
                free(cur);
                head = next;
                cur = next;
            }
            else
            {
                prev->next = next;
                free(cur);
                cur = NULL;
                cur = next;
            }
        }
        else //找不到val就让cur prev 一起往后移动
        {
            prev = cur;
            cur = next;
        }
    }
    return head;
}

自己一开始写的，比较挫。

struct ListNode *removeElements(struct ListNode *head, int val)
{
    struct ListNode *prev = NULL;
    struct ListNode *cur = head;
    while (cur)
    {
        while (cur != NULL && cur->val != val)
        {
            prev = cur;
            cur = cur->next;
        }
        //考虑链表中一个val都没有时，这样cur就会走到空，要先保证cur不为空，才解引用cur判断是否为val
        if(cur == NULL)
        {
            break;
        }
        //必须确保cur当前指向的是val时才进行删除，可能链表里一个val都没有
        if (cur->val == val)
        {
            //考虑第一个节点就是val的情况
            if (prev == NULL)
            {
                //临时保存cur的下一个节点的位置
                struct ListNode *next = cur->next;
                head = next;
                free(cur);
                cur = NULL;
                cur = next;
            }
            else
            {
                //出来时cur指向的就是val那个节点
                prev->next = cur->next;
                free(cur);
                cur = NULL;
                cur = prev->next;
            }
        }
    }
    return head;
}

带哨兵位：

强行开辟一个哨兵位的头结点，这样prev就不会出现空指针解引用的问题了。

注意手动开辟的guardHead一定要手动释放。

struct ListNode *removeElements(struct ListNode *head, int val)
{
    //强行开辟一个哨兵位的头结点
    struct ListNode* guardHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    guardHead->next = head;
    struct ListNode* cur = head;
    struct ListNode* prev = guardHead;
    while(cur)
    {
        //提前记录cur的下一个节点
        struct ListNode* next = cur->next;
        //相等时，让prev指向next
        if(cur->val == val)
        {
            prev->next = next;
            free(cur);
            cur = NULL;
            cur = next;
        }
        //不相等的时候，prev cur都往前走
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    head = guardHead->next;
    free(guardHead);//开辟出来的东西一定要手动释放掉，不然会存在内存泄漏
    guardHead = NULL;
    return head;
}

NO2. 反转链表

三指针翻转：

其实只要把箭头翻过来就行。

n1指向NULL，n2指向第一个节点，

但是这样n2就找不到下一个节点了，因此还需n3来指向n2的下一个。

n2指向n1，然后n2赋值给n1，n3赋值给n2，n3往后移动

n2指向NULL时就结束了，n1就是新链表的头，

注意n3指向NULL时可能会产生空指针解引用。

注意还要考虑极端情况，空链表或只有一个结点的情况。

struct ListNode* reverseList(struct ListNode* head)
{
    //考虑空链表或只有一个结点的极端情况，此时都有空指针解引用的风险
    if(head == NULL || head->next == NULL)
        return head;
    struct ListNode *n1 = NULL, *n2 = head, *n3 = head->next;
    while(n2)
    {
        //翻转
        n2->next = n1;
        //迭代
        n1 = n2;
        n2 = n3;
        //注意n3 空指针解引用的情况，n3指向NULL不能再走了
        if(n3 != NULL)
            n3 = n3->next;
    }
    //n1就是新链表的头结点
    head = n1;
    return head;
}

头插法：

这里的头插不需要创建新节点。
取原链表中的节点，头插到新节点。

把cur拿下来的同时，还需保存cur的next，不然插下来之后就找不到了。

迭代记录next的位置，并让cur指向newHead。头插的节点要变成新的头。

考虑空链表和一个节点的情况，发现恰巧也能满足。

struct ListNode* reverseList(struct ListNode* head)
{
    //头插法，把每一个节点拿下来，头插到新的节点里面。
    struct ListNode* newHead = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        //一开始newHead是NULL
        struct ListNode* next = cur->next;
        cur->next = newHead;
        newHead = cur;
        cur = next;
    }
    head = newHead;
    return head;
}

递归：

在稿纸上画图分析就行，递归核心就是假设后面n-1个已经翻转了

以链表1->2->3->4->5举例
先去到最后一个节点5，然后让5指向4，4要指向空

//1->2<-3<-4<-5
//而且第一个要指向NULL
struct ListNode* reverseList(struct ListNode* head)
{
    //递归
    if(head == NULL || head->next == NULL)
    {
         /*
         直到当前节点的下一个节点为空时返回当前节点
         由于5没有下一个节点了，所以此处返回节点5
         */
        return head;
    }
    struct ListNode* cur = head;
    struct ListNode* next = cur->next;
    //递归传入下一个节点，目的是为了到达最后一个节点
    struct ListNode* newHead = reverseList(next);
    //要让cur的下一个翻转过来指向cur
    next->next = cur;//第二轮递归中，next就是5，cur是4，让5指向4，4指向空
    cur->next = NULL;
    return newHead;//每一轮递归返回都是节点5
}

开数组：

观察题目节点的数据范围，额外开一个数组。存放所有的val，借助count翻转所有的val即可

特殊情况，链表为空或单个节点，也能满足

struct ListNode* reverseList(struct ListNode* head)
{
    //开数组
    int array[5010] = {0};
    struct ListNode* cur = head;
    //把原链表中每一个节点的val放到数组中去，并计数
    int count = 0;
    int i = 0;
    while(cur)
    {
        count++;
        array[i++] = cur->val;
        cur = cur->next;
    }
    //再借助count 把原链表的val翻转过来
    cur = head;
    count--;//count的数比数组下标多1
    while(cur)
    {
        cur->val = array[count--];
        cur = cur->next;
    }
    return head;
}

NO3. 链表的中间结点

两次循环：

借助count统计链表节点个数，第二次循环时只遍历n/2即可

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        //题目说了非空，但要考虑只有一个节点的情况
        if(head->next == NULL)
            return head;
        //2遍循环，第一遍统计节点个数
        int count = 0;
        ListNode* cur = head;
        while(cur)
        {
            count++;
            cur = cur->next;
        }
        //cur要重置
        cur = head;
        count = count / 2;
        while(count--)
        {
            cur = cur->next;
        }
        return cur;
    }
};

数组：

对链表进行遍历，同时将遍历到的元素依次放入数组 A 中。如果我们遍历到了 N 个元素，那么链表以及数组的长度也为 N，对应的中间节点即为 A[N/2]

class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        vector<ListNode*> A = {head};
        while (A.back()->next != nullptr)
            A.push_back(A.back()->next);
        return A[A.size() / 2];
    }
};

快慢指针：

如果只能遍历一遍链表呢？

利用快慢指针，快指针一次走2步，慢指针一次走一步，当fast指向NULL或者fast的下一个指向NULL
由于题目要求，偶数个返回中间的第二个节点，恰好就是slow

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *fast = head, *slow = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

NO4.链表中倒数第k个节点

牛客

暴力循环：

//力扣上的OJ
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
    //求链表长度
    int len = 0;
    struct ListNode* cur = head;
    while(cur != NULL)
    {
        cur = cur->next;
        len++;
    }
    //倒数第k个就是正数第len-k次访问
    for(int i=0; i<len-k; i++)
    {
        head = head->next;
    }
    return head;
}

注意，牛客的题细节更多，需要考虑更多情况。

上面代码在牛客就跑不过。

考虑k <= 0 或者空链表的情况

考虑节点的总个数 < k

class Solution
{
public:
    ListNode *FindKthToTail(ListNode *pListHead, unsigned int k)
    {
        //注意考虑k <= 0 或者空链表的情况
        if (pListHead == NULL || k <= 0)
            return nullptr;

        //先求出节点个数
        int count = 0;
        ListNode *cur = pListHead;
        while (cur)
        {
            count++;
            cur = cur->next;
        }
        //考虑节点的总个数 < k
        if (count < k)
            return nullptr;
        //倒数第1个，正数第5个。倒数第2个，正数第4个  --》count -k +1 ??
        //错，注意cur已经包含当前的第一个了，因此需要再-1 也就是count -k
        //需要重置cur
        cur = pListHead;
        count -= k;
        while (count--)
        {
            cur = cur->next;
        }
        return cur;
    };
};

快慢指针：

首先让快指针先行k步，然后让快慢指针每次同行一步，直到快指针指向空节点，慢指针就是倒数第K个节点。

当然 fast先走k-1步也是可以的，相应的，slow fast一起走的时候fast结束位置就要改变一下

注意考虑空链表以及k>链表长度以及k为负数的问题

//力扣上的OJ
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
    //快慢指针
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    //fast先走k步
    while(k--)
    {
        //考虑空链表以及k>链表长度的问题
        if(fast == NULL)
            return NULL;
        fast = fast->next;
    }
    //快慢同时走
    while(fast != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

牛客的OJ很恶心，很难调
1.自测常规情况，可以过
2.打印一些标记值，不显示输出标记值。比如:段错误
3.思考极端情况场景测试用例(链表为空，k大于链表长度，k为负数等等)

力扣环境很舒服，错了会报测试用例，根据测试用例去改就行

牛客体验相当糟糕，报错报的很模糊

class Solution
{
public:
    ListNode *FindKthToTail(ListNode *pListHead, unsigned int k)
    {
        //链表为空或者k为负
        if (pListHead == nullptr || k <= 0)
            return nullptr;
        ListNode *slow = pListHead, *fast = pListHead;
        while (k--)
        {
            fast = fast->next;
            //fast 走到空了但k还没走完
            if(fast == nullptr)
                return nullptr; //如果单链表长度 < K，直接返回
        }
        while (fast) //fast走到空就结束了
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

尾声 🐶

🌵🌵

写文不易，如果有帮助烦请点个赞~ 👍👍👍

🌹🌹Thanks?(･ω･)ﾉ🌹🌹

👀👀由于笔者水平有限，在今后的博文中难免会出现错误之处，本人非常希望您如果发现错误，恳请留言批评斧正，希望和大家一起学习，一起进步ヽ(￣ω￣(￣ω￣〃)ゝ，期待您的留言评论。
附GitHub仓库链接