【初阶数据结构】单链表基础OJ题讲解

前言

📚作者简介：爱编程的小马，正在学习C/C++，Linux及MySQL。

📚本文收录与初阶数据结构系列，本专栏主要是针对时间、空间复杂度，顺序表和链表、栈和队列、二叉树以及各类排序算法，持续更新！

📚相关专栏C++及Linux正在发展，敬请期待！

前言

1. 单链表基础OJ题讲解

1.1 第一题

1.2 第二题

1.3 第三题

1.4 第四题

1.5 第五题

总结

1. 单链表基础OJ题讲解

首先，经过上一篇博客的学习，相信同学们已经对顺序表的基础OJ题有了一定的了解，那么本文继续带着大家一起来刷力扣的单链表基础题。

1.1 第一题

第一题题目链接：移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

题目分析：我画个图给大家看一下，就是如何来分析。

就是和val相同的就移除，不相同的就保留，返回新的头结点。

思路（大家最容易想到的）：

拷贝，等于val我就不拷贝，不等于val的就拷贝到新链表，最后是不是返回新链表就可以，那么这个地方我用newhead和list来管理新链表。我画个图给大家看一下：

代码实现如下：

struct ListNode* removeElements(struct ListNode* head, int val) 
{
    struct ListNode* newhead = NULL;
    struct ListNode* list = NULL;
    while(head)
    {
        if(head->val == val)
        {
            head = head ->next;
        }
        else
        {
            if(newhead == NULL)
            {
                newhead = head;
                list = head;
                head = head->next;
                list->next = NULL;
            }
            else
            {
                list->next = head;
                head = head->next;
                list = list->next;
                list->next = NULL;
            }
        }
    }
    return newhead;
}

1.2 第二题

第二题题目链接：翻转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

题目分析：

思路：

也是可以拷贝，如何拷贝呢？是不是还是建立一个新的一个链表newhead，然后尾插head链表中的节点是不是就可以了?

代码实现：

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;

    while(cur)
    {
        if(newhead == NULL)
        {
            head = head->next;
            newhead = cur;
            newhead ->next = NULL;
            cur = head;
        }
        else
        {
            head = head->next;
            cur->next = newhead;
            newhead = cur;
            cur = head;
        }
    }
    return newhead;
}

1.3 第三题

第三题题目链接：链表的中间节点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

题目分析：

这道题有个很巧的方法，就是用两个指针，一个是快指针，一个是慢指针，快指针一次走两步，慢指针一次走一步，那么快指针走完是不是慢指针只走了一半，直接返回慢指针就可以了。

代码实现：

struct ListNode* middleNode(struct ListNode* head) 
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

1.4 第四题

第四题题目链接：返回倒数第K个节点

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值

就是首先得先找到这个链表的尾部，然后head这个指针找到离最后一个tail指针为k的地方，返回这个地方的值，我建议大家用count这个变量来记录。

代码实现：

int kthToLast(struct ListNode* head, int k)
{
    int count = 0;
    struct ListNode* tail = head;
    while(tail)
    {
        tail = tail->next;
        count++;
    }
    while(count-k)
    {
        head = head->next;
        count--;
    }
    int m = head->val;
    return m;

}

1.5 第五题

第五题题目链接：合并两个有序链表

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

题目分析：

这道题是这样子，还是建立一个新链表，用newhead和cur来管理，然后遍历list1和list2，谁小谁就放进去，如果有一个链表结束了，那就把另一个链表是不是直接拷贝过去就可以。

代码实现：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;
    struct ListNode* newhead = NULL;
    struct ListNode* cur = NULL;
    while(list1 && list2)
    {
       if(list1->val < list2->val)
       {
            if(newhead == NULL)
            {
                newhead = list1;
                cur = list1;
                list1 = list1->next;
                cur ->next = NULL;
            }
            else
            {
                cur -> next = list1;
                list1 = list1->next;
                cur = cur->next;
            }
       }
        else
        {
            if(newhead == NULL)
            {
                newhead = list2;
                cur = list2;
                list2 = list2->next;
                cur ->next = NULL;
             }
            else
            {
                cur -> next = list2;
                list2 = list2->next;
                cur = cur->next;
            }
        }  
    }
    if(list1)
    {
        cur->next = list1;
    }
    if(list2)
    {
        cur->next = list2;
    }
    return newhead;
}