数据结构算法题(力扣)——链表

以下题目建议大家先自己动手练习,再看题解代码。这里只提供一种做法,可能不是最优解。

1. 移除链表元素(OJ链接

题目描述:给一个链表的头节点 head 和一个整数 val ,删除链表中所有满足值等于 val 的节点,并返回新的头节点

解法:遍历链表,依次比对结点的值和val是否相等,相等则删除,不相等则更新指针指向,继续遍历。

这里需要分两种情况来讨论,一是链表结点的值都等于val,二是链表结点的值不都等于val。

struct ListNode* removeElements(struct ListNode* head, int val) 
{
    //全部结点的值都等于val或前面部分结点相等
    while(head&&head->val==val)
    {
        head=head->next;
    }
    //删除全部结点后head为空或者链表本身就为空链表
    if(!head)
    {
        return NULL;
    }
    
    struct ListNode* cur=head;
    while(cur->next)
    {
        //cur的下一个结点值等于val,则删除下一个
        if(cur->next->val==val)
        {
            cur->next=cur->next->next;
        }
        //不相等则cur后移一步
        else
        {
            cur=cur->next;
        }
    }
    return head;
}

无论链表结点中是什么样的值,当进行完第一个while循环后,如果head不是NULL,那么我们定义的cur指针指向的结点的值一定不等于val。因此第二个while循环里if的判断条件为cur->next->val==val,这样不需要保留cur的前一个结点,因为cur本身就是前一个结点(可能删除的结点的前一个结点)。

2. 反转链表(OJ链接

题目描述:给定单链表的头节点 head ,反转链表,并返回反转后的链表的头节点。

我们所要做的操作如下图
在这里插入图片描述
如果链表为NULL,直接返回空即可。链表不为空,则需要反转。

以上图链表为例本题解法如下图所示。
在这里插入图片描述

当n2为空时,循环结束。

题解代码如下

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

注意题解中的prev,cur和next指针分别对应图中的n1,n2,n3。最后一步时n3为NULL,所以需要加判断语句。

3. 链表的中间结点(OJ链接

题目描述:给定单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

如果链表结点个数为奇数,返回中间结点,如果结点数为偶数,返回第二个结点。比如有六个结点,则返回第四个结点。

解法:快慢指针法。指的是一个指针走的步数多,一个指针走的步数少。此题快指针走两步,慢指针走一步。当快指针走到NULL或最后一个结点时(链表结点数为偶数或奇数),慢指针指向的结点即为中间结点。

题解代码如下

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

4. 合并两个有序链表(OJ链接

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

解法:创建两个指针变量分别指向两个链表的头,依次比较结点的值,值小的结点链接到新链表的尾,依次遍历链表,其中一个链表走完后,将剩余的链表链接到新链表的尾即可。

示例:
在这里插入图片描述
题解代码如下

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (!list1) 
    {
        return list2;
    }
    if (!list2) 
    {
        return list1;
    }
    //分别指向两个链表的头结点
    ListNode *p1 = list1, *p2 = list2;
    //phead为新链表的头,ptail为新链表的尾
    ListNode *phead = NULL, *ptail = NULL;
    //两个链表都没有遍历完
    while (p1 && p2) 
    {
        if (p1->val < p2->val) 
        {
            //链接的是第一个结点
            if (phead == NULL) 
            {
                phead = ptail = p1;
                p1 = p1->next;
            } 
            else 
            {
                ptail->next = p1;
                ptail = ptail->next;
                p1 = p1->next;
            }
        } 
        else 
        {
            //链接的是第一个结点
            if (phead == NULL) 
            {
                phead = ptail = p2;
                p2 = p2->next;
            } 
            else 
            {
                ptail->next = p2;
                p2 = p2->next;
                ptail = ptail->next;
            }
        }
    }
    //链表1没有走完
    if (p1) 
    {
        ptail->next = p1;
    }
    //链表2没有走完
    if (p2) 
    {
        ptail->next = p2;
    }
    return phead;
}

5. 返回倒数第k个结点(OJ链接

题目描述:给定一个单链表的头结点(head),找出单向链表中倒数第 k 个节点。返回该节点的值。

此题和第三题类似。解法依旧是快慢指针法

解法:快指针先走k步,然后和慢指针一起走,快指针走到NULL时,慢指针指向的结点就是倒数第k个结点。
原理:快指针先走k步,使得两个指针间隔为k。再一起以相同速度走,最后两个指针间隔依旧是k

题解代码如下

int kthToLast(struct ListNode* head, int k)
{
    struct ListNode* fast=head,*slow=head;
    while(k--)
    {
        fast=fast->next;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow->val;
}

这里就先介绍这五个题的做法,大家可以试试用别的做法看是否可以做出来噢。

相关推荐

最近更新

  1. leetcode705-Design HashSet

    2024-04-04 01:10:03       8 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-04 01:10:03       8 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-04 01:10:03       9 阅读
  4. 高级IO——React服务器简单实现

    2024-04-04 01:10:03       8 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-04 01:10:03       7 阅读
  6. go第三方库go.uber.org介绍

    2024-04-04 01:10:03       8 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-04 01:10:03       10 阅读

热门阅读

  1. Collection中常用方法

    2024-04-04 01:10:03       4 阅读
  2. redis

    2024-04-04 01:10:03       3 阅读
  3. Yocto理论基础之layer

    2024-04-04 01:10:03       4 阅读
  4. 网络安全专业术语

    2024-04-04 01:10:03       4 阅读
  5. 蓝桥杯刷题--python-36

    2024-04-04 01:10:03       2 阅读