[数据结构与算法][数据结构]一文带你练习常见链表OJ题

?作者简介：大家好我是zoroxs
📃个人主页：c/c++学习之路
🔥💖如果觉得博主的文章还不错的话，请👍三连支持一下博主哦

本文是带读者做一些常见的链表OJ题,检验一下自己的链表是否基础扎实

📕删除链表中等于给定值 val 的所有节点 (leetcode 203)

分析

看到这个题,大家一定会想到的思路就是
1.创建一个新的头节点,不是val的就尾插下来, 把是val的 free 掉.

有几种特殊情况需要特殊处理,

1. 链表为空,直接返回NULL
2. 链表中所有的值都是val ,一样也是返回NULL

大家可以自己推导一下执行过程,数据结构学习的过程必须要画图和思考,画图比写代码困难.
所以我们找到第一个不是val的节点之后,就可以继续向后找

下面看代码

struct ListNode* removeElements(struct ListNode* head, int val)
{
    if(NULL == head)
    {
        return NULL;
    }

    struct ListNode* cur = head;
    //1.找到第一个不是val的结点
    while(cur && cur->val == val)
    {
        struct ListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    //判断循环以哪种方式结束, 如果NULL == cur,说明链表中的值都等于val 直接返回NULL;
    if(NULL == cur) 
    {
        return NULL;
    }

    //走到这里, cur的位置就是第一个值 != val 的节点
    struct ListNode* newHead = cur;
    struct ListNode* newTail = cur;

    //当前cur位置已经给到了newHead和newTail  , 所以cur需要往后指一个
    cur = cur->next;
    while(cur)
    {
        struct ListNode* next = cur->next;
        //1.如果相等,继续释放
        if (val == cur->val)
        {   
            free(cur);
        }
        else  //2.不相等就尾插
        {
            newTail->next = cur;
            newTail = newTail->next;
        }
        cur = next;
    }
    //把尾指向的置空  
    newTail->next = NULL;
    return newHead;
}

📗反转一个单链表 (leetcode 206)

1??思路一

定义一个新的头节点,把原链表中的每一个元素头插进去,得到的就是反转后的链表

学习数据结构的时候,一定要画图,画图,一步步用图来执行,就把伪代码同样写出来了
来看一下代码实现

struct ListNode* reverseList(struct ListNode* head)
{
    if(NULL == head)
    {
        return NULL;
    }
    struct ListNode* cur = head;
    struct ListNode* newHead  = NULL;   
    while(cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newHead;
        newHead = cur;
        cur = next;
    }
    return newHead;
}

2??思路二

这不就是我们想要的结果吗

大家来看代码

struct ListNode* reverseList(struct ListNode* head)
{
    if (NULL == head)
    {
        return head;
    }
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    
    while(cur)
    {
        struct ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

大家一定要画图+ 思考,代码很简单,关键是画图模拟执行流程

📘给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点

看到这个题,大家很容易想到的思路就是
计算链表的长度,然后算出长度的一半,从头开始走,走一半,刚好是中间节点

这个方法固然可以做,我在这里就不实现了,大家可以自己尝试一下,不难
这里给大家提出一种新的思路,玩链表必会,快慢指针

我们定义两个指针 ,fast slow ,都从头开始走, fast一次走两步, slow 一次走一步, 当fast走到结尾的时候,slow是不是刚好走到中间位置呢
我们来分析一下

看一下代码

struct ListNode* middleNode(struct ListNode* head)
{
    if(NULL == head)
    {
        return NULL;
    }
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    //因为fast一次走两步, 所以fast->next也不能为空,不然会有空指针异常
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    //返回慢指针
    return slow;
}

📙输入一个链表，输出该链表中倒数第k个结点

看到这个题,第一个想到的还是算链表的长度,然后找到倒数第k个节点,虽然复杂度也是O(N)
但是我们了解了快慢指针,就可以朝着这方面去想

定义两个指针,fast slow

来看一下代码

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    //判断链表是否为空
    if(NULL == pListHead)
    {
        return NULL;
    }
    //判断k是否合法
    if(k <= 0 )
    {
        return NULL;
    }
    struct ListNode* fast = pListHead;
    struct ListNode* slow = pListHead;
    //让fast先走k步
    while(k--)
    {
        //如果k大于链表的长度,那么这里fast会变成空
        if(NULL == fast)
        {
            return NULL;
        }
        fast = fast->next;
    }
    //他俩同时走,fast为空的时候,slow就是结果
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

📓将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

相信大家看到这个题一定不陌生,肯定做过一道题,两个有序数组合并成一个数组,没做过的可以去做一个.
这里用的思想和那个一样, 都是归并, 只不过链表这里不需要开辟新的空间

我们可以使用malloc 开辟一个哨兵位的头结点,不存储有效数据,来方便操作,但是使用完了之后一定要记得释放

分析一下

直接来看代码

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(NULL == list1)
    {
        return list2;
    }
    if(NULL == list2)
    {
        return list1;
    }
    
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;
    struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* newTail = newHead;
    while(cur1 && cur2)
    {
        if(cur1->val < cur2->val)
        {
            //把cur1尾插到新链表
            struct ListNode* next = cur1->next;
            newTail->next = cur1;
            newTail = newTail->next;
            cur1 = next;
        }
        else
        {
            //把cur2尾插到新链表
            struct ListNode* next = cur2->next;
            newTail->next = cur2;
            newTail = newTail->next;
            cur2 = next;
        }
    }
    //走到这里,说明有一个链表已经结束
    if(cur1)
    {
        //直接把剩下的拼接过去
        newTail->next = cur1;
    }
    if(cur2)
    {
        //直接把剩下的拼接过去
        newTail->next = cur2;
    }
    
    struct ListNode* next = newHead->next;
    free(newHead);
    return next;

}

📔编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

看到这个题,做题选项没有C语言,所以选了c++ ,因为c++是兼容C语言的
首先要求是不能改变原来的顺序,如果可以改变我们可以怎么解??
弄一个新链表,小于x的就头插过去,其他的尾插过去就可以解了

这里要求顺序,我们可以定义两个新的链表,开辟两个哨兵位,不存储数据,
一个尾插小于x的,另一个尾插其他的, 然后把两个链表拼接起来就OK了

如果不把greaterTail置空,就会成环

看代码

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {

        if(NULL == pHead)
        {
            return NULL;
        }
        ListNode* lessHead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* greaterHead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* lessTail = lessHead;
        ListNode* greaterTail = greaterHead;

        ListNode* cur = pHead;
        while(cur)
        {
            ListNode* next = cur->next;
            if(cur->val < x)
            {
                //尾插到less链表
                lessTail->next = cur;
                lessTail = lessTail->next;
                cur = next;
            }
            else
            {
                //尾插到greater链表
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
                cur = next;
            }
        }
        //拼接起来
        lessTail->next = greaterHead->next;
        //避免成环
        greaterTail->next = NULL;

        //释放空间
        free(greaterHead);
        ListNode* next = lessHead->next;
        free(lessHead);
        return next;
    }
};

📒链表的回文结构

看到这个题,非常熟悉吧,什么回文字符串,回文数字… 现在变成了回文链表
因为是单向无头不循环链表,所以无法往前找,所以就得想别的方法

这里要求时间复杂度O(n) ,空间复杂度为O(1)

最初的思路是,先正向把链表中的值挨个放到一个数组中,然后反转链表,挨个对比
但是这样会开辟一个数组,长度和链表长度一样, 虽然题目说链表长度小于900,但是空间复杂度是O(N)

我们想一下前面做的题,我们可不可以找到中间节点,然后把中间节点之后的反转一下,这不就是刚好可以两个链表比较了吗

我们来分析一下

我们来用代码实现一下

class PalindromeList {
public:
bool chkPalindrome(ListNode* A) 
{
    if(NULL == A)
    {
        return false;
    }
        //1.找中间节点
        ListNode* fast = A;
    ListNode* slow = A;
    while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
    //slow当前指向的是中间节点


    //2.反转链表
    ListNode* cur = slow;
    ListNode* midHead = NULL;
    while(cur)
        {
            ListNode* next = cur->next;
            cur->next = midHead;
            midHead = cur;
            cur = next;
        }    
    //反转结束,中间链表的头是midHead

    cur = A;
    ListNode* mid_cur = midHead;
    while(mid_cur) //以中间链表的结束为标记
    {
        if(cur->val != mid_cur->val)
         {
               return false;
        }
                cur = cur->next;
                mid_cur = mid_cur->next;
    }
            return true;
	}
};

📚输入两个链表，找出它们的第一个公共结点

看到这个题,首先就能想到的解法是O(N^2),A的节点挨着去B链表中找,这样可以实现,但是复杂度过高,过于浪费时间,大家可以自己实现一下

在这里,我们可以把问题分解成2个问题

1. 判断链表是否相交
2. 如果链表相交返回交点,不相交返回NULL

我们首先想一下如何能判断链表是否相交

注意到,链表相交的最后结果,是两个链表交到一起,就像两个水流汇在一起,所以他们的最后一个节点一定是相同的
所以我们可以这样判断:
如果两个链表最后一个节点相同,那么他们一定相交,反之则不然

那么如果相交的话,如何判断交点呢?
如果是这样的两个链表,我们很容易找到交点

因为长度相同,只需要并行往后走,就可以找到交点

如果链表相交,那么后半部分一定是相同的,所以只需要操作前半部分
我们可以计算链表的长度,让长的链表先走 长度差值步,然后再一起走,不就相当于并行了么

看一下代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    if(NULL == headA || NULL == headB)
    {
        return NULL;
    }   
    //1.判断是否相交,顺便求出两个链表长度
    int lenA = 0;
    int lenB = 0;
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    //找尾
    while(curA->next)
    {
        lenA++;
        curA = curA->next;
    }
    while(curB->next)
    {
        lenB++;
        curB = curB->next;
    }
    //判断是否相交
    if(curA != curB)
    {
        //说明没有交点
        return NULL;
    }

    //寻找交点,让长链表先走差值步
    //假设a长
    struct ListNode* l1 = headA;
    struct ListNode* l2 = headB;
    if(lenA < lenB)
    {
        l1 = headB;
        l2 = headA;
    }
    int tmp = abs(lenA-lenB);
    while(tmp--)
    {
        //让长链表先走差值步
        l1 = l1->next;
    }
    //并行
    while(l1 != l2)
    {
        l1 = l1->next;
        l2 = l2->next;
    }
    return l1;
}

📃给定一个链表，判断链表中是否有环。

这个题的思路可以有很多,有破解版–>如果链表走了10000多次还没停下来,说明有环(不正经解法)
第二种 我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

我们这里采用另一种,龟兔赛跑(快慢指针).

定义两个指针,一个为fast 一个为slow ,如果链表中有环,他俩一定会相遇

请看证明过程

我们来看一下代码

bool hasCycle(struct ListNode *head) 
{
    if(NULL == head)
    {
        return NULL;
    }    
    
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        //说明追上了
        if(fast == slow)
        {
            return true;
        }
    }
    return false;
}

大家应该有些疑问,为什么fast要走两步,fast走3步,fast走4步不行吗? 走n步呢??

📃给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

这个题一眼看过去,没有思路,我们画图慢慢分析一下

1??思路一

我们来写一下代码

struct ListNode *detectCycle(struct ListNode *head) 
{
    if(NULL == head)
    {
        return NULL;
    }
    //判断是否有环
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        
        if(fast == slow)
        {
            //相遇节点  ,以meet为新的结尾,变成两个链表求交点的问题
            struct ListNode* meet = fast;
            struct ListNode* next = meet->next;

            meet->next = NULL;
            return getIntersectionNode(head, next);
        }
    }
    return NULL;
}

2??思路二

这里还有另一种思路
一个从相遇节点meetNode往后走,另一个从头开始走,他们会在环的入口点相遇

我们来证明一下

所以一个从头开始走,另一个从meetNode开始走,会在环的入口点相遇
看代码

struct ListNode *detectCycle(struct ListNode *head) 
{
    if(NULL == head)
    {
        return NULL;
    }
    //判断是否有环
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        
        //说明fast追上slow-->有环
        if(fast == slow)
        {
            //相遇节点
            struct ListNode* meet = fast;
            struct ListNode* cur = head;
            //相遇节点往下走,与头结点往后走,会在环的入口相遇
            while(meet != cur)
            {
                meet = meet->next;
                cur = cur->next;
            }
            return meet;
        }
    
    }
    return NULL;
}

📚8.总结

学习数据结构的过程中,一定要画图与思考并进,多思考多画图,多写代码
如果大家有什么问题,可以私信我

🔥💖如果觉得博主的文章还不错的话，请👍三连支持一下博主哦