单链表在线OJ题(详解+图解)

简介: 单链表在线OJ题(详解+图解)
1.删除链表中等于给定值 val 的所有节点

本题的要求是输入一个val的整形值,若链表中节点存储的值与val相等,则删除这个节点,并最后返回这个删除节点后的链表,思路如下:

我们可以直接使用while循环,并且使用双指针的方法,当这个当前节点的值与value相等时,我们就可以使用我们存储的prev(也就是cur前面一个节点)来删除当前cur节点,令prev的next等于cur的next,同时cur也要记得往后移动,while循环的终止条件就是当cur为空时就不进去,此时prev就时链表的尾节点,函数最终返回的依然是head节点

代码如下:

当head不为空时,且head所存放的值和val相等时,就直接可以将head往后移动

struct ListNode* removeElements(struct ListNode* head, int val)
{
  while (NULL != head && head->val == val)
  {
      head = head->next;
  }
  struct ListNode* curr=head;
  struct ListNode* prev=NULL;
  while(curr!=NULL)
  {
      if(curr->val!=val)
      {
          prev=curr;
      }
      else
      {
          prev->next=curr->next;
      }
      curr=curr->next; 
  }
  return head;
}
2.反转一个单链表

本题的意思很简单,就是将其反转:

我们要将链表反转,就是说将链表的“箭头”反过来

所以,到这里我们可以用while循环和两个指针来解决问题,首先将cur定位head位置(也就是第一个节点),同时prev是为空的,我们首先将节点1的next置为NULL,然后就是将2的next置为1节点所以我们在循环里要再cur移动之前就将2节点的指针存储好,我们将其定为next(cur->next),将1的next置为prev后,然后将prev置为cur,我们还要将cur往后移动,直接令cur=next,这样才能保证prev时cur的前一个节点,最后返回prev,prev就是最后一个节点,反转后的第一个节点

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* prev=NULL;
    struct ListNode* cur=head;
    while(cur)
    {
        struct ListNode* next=cur->next;
        cur->next=prev;
        prev=cur;
        cur=next;
    }
    return prev;
}
3.给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点

这种题目我们首先可以想到的就是快慢指针,我们定义两个指针,一个位slow,一个位fast,slow一次走一步,fast一次走两步,直到fast或者fast的next为空时就不能走了,slow的位置就是链表的中间节点了,因为fast走的距离就是slow的二倍

代码如下:

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}
4.输入一个链表,输出该链表中倒数第k个结点

这一题我们同样可以用快慢指针的方式来解决,我们先让fast指针先走k步,然后 fast和slow再一起一次走一步,最后当fast为空时,slow就是倒数第k个节点了

代码如下:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
    struct ListNode* slow=pListHead;
    struct ListNode* fast=pListHead;
    while(k--)
    {
        if(fast==NULL)
            return NULL;
        fast=fast->next;
    }
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;   
    }
    return slow;
}
5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

合并两个有序链表为一个有序链表,之前顺序表我们做过一个类似的题目,这里我们可以首先考虑两种简单的情况:当链表1或者链表2分别为空时,返回非空的那个即可,当两个同时为空时,直接返回空。

然后我们就 开始比较两个链表的第一个节点的值的大小,取较小的那个节点所属的链表为新链表的第一个节点和尾节点,然后再将两个链表的值进行比较,较小的一个节点就首先放在tail的next位置,然后将tail移动到较小的这个节点,同时较小节点的list=list->next

代码如下:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* head=NULL;
    struct ListNode* tail=NULL;
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    while(list1&&list2)
    {
        
        if(list1->val<list2->val)
        {
            if(tail==NULL)
            {
                head=tail=list1;
            }
            else
            {
                tail->next=list1;
                tail=tail->next;
            }
            list1=list1->next;
        }
        else
        {
            if(tail==NULL)
            {
                head=tail=list2;
            }
            else
            {
                tail->next=list2;
                tail=tail->next;
            }
            list2=list2->next;
        }
    }
        if(list1)//list2遍历完成,list1遍历没完成,就直接把list2直接接上去
        {
            tail->next=list1;
        }
        if(list2)
        {
            tail->next=list2;
        }
    return head;
}
6.编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前

本题我们可以首先申请一个小于x的链表的空间存储小于x的节点 ,另外 申请一个大于x的链表,然后再将首节点置为小于x链表的首节点,将小于x链表的尾节点和大于x的链表的首节点链接,最后返回首节点即可

代码如下:

ListNode* partition(ListNode* pHead, int x) 
    {
        //大于等于x的尾插到一个列表,小于x的尾插到另一个列表
        struct ListNode* lesshead,*lesstail,*greaterhead,*greatertail;
        lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
        greaterhead=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                lesstail->next=cur;
                lesstail=lesstail->next;
            }
            else 
            {
                greatertail->next=cur;
                greatertail=greatertail->next;
            }
            cur=cur->next;
        }
        //注意:这里用到了哨兵位,也就是说,两个链表的头节点都没有存储有效的数据
        lesstail->next=greaterhead->next;
        greatertail->next=NULL;
        pHead=lesshead->next;
        free(lesshead);
        free(greaterhead);
        return pHead;
    }
7.链表的回文结构

本题我们就要将链表一分为二了,然后再用循环进行比较,如果出现不相等,就直接返回false,否则返回true,若链表为空直接返回 false,我们用快慢指针,fast一次走两步,slow一次走一步,然后将slow前的节点所组成的链表进行反转,与slow后节点的链表进行比较即可

代码如下:

bool chkPalindrome(ListNode* A) 
    {
        if(A==NULL)
            return false;
        ListNode* slow=A,*fast=A;
        while(fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode* cur=NULL,*next=slow;
        while(slow)
        {
            next=slow->next;
            slow->next=cur;
            cur=slow;
            slow=next;
        }
        next=A;
        while(cur)
        {
            if(next->val!=cur->val)
                return false;
            next=next->next;
            cur=cur->next;
        }
        return true;
    }

好了,今天的分享到这里就结束了,谢谢大家的支持!

相关文章
|
6月前
|
算法 C语言
【数据结构与算法 经典例题】链表的回文结构(图文详解)
【数据结构与算法 经典例题】链表的回文结构(图文详解)
|
7月前
|
算法
详解单链表经典OJ题-2
详解单链表经典OJ题
38 2
|
7月前
详解单链表经典OJ题-1
详解单链表经典OJ题
28 2
|
7月前
|
存储
单链表在线OJ题二(详解+图解)
单链表在线OJ题二(详解+图解)
33 1
|
7月前
顺序表在线OJ题(详解+图解)
顺序表在线OJ题(详解+图解)
49 1
|
7月前
二叉树在线OJ
二叉树在线OJ
49 1
|
7月前
|
存储 容器
二叉搜索树在线OJ题讲解
二叉搜索树在线OJ题讲解
33 0
|
7月前
|
存储 索引
链表(基础详解、实现、OJ笔试题)
链表(基础详解、实现、OJ笔试题)
|
7月前
|
索引
单链表经典OJ题(三)
单链表经典OJ题(三)
|
7月前
单链表经典OJ题(二)
单链表经典OJ题(二)