首页 > 其他分享 >单链表题带刷(二)

单链表题带刷(二)

时间:2024-10-30 18:20:52浏览次数:3  
标签:表题 单链 ListNode struct int next 链表 n1

目录

一、链表的回文结构

1.1 题目

1.2 解题思路

二、相交链表

2.1 题目


一、链表的回文结构

1.1 题目

https://www.nowcoder.com/share/jump/6870342311730273670970icon-default.png?t=O83Ahttps://www.nowcoder.com/share/jump/6870342311730273670970

1.2 解题思路

思路一:创建新链表,将原链表反转并保存在新链表里,在将新旧链表比较

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstddef>
class PalindromeList 
{
public:
    bool chkPalindrome(ListNode* A) 
    {
        struct ListNode* ne = A;
       struct ListNode* n1 = NULL;
       struct ListNode* n2 = ne;
       struct ListNode* n3 = ne->next;
       while(n2)
       {
          n2->next = n1 ;
          n1 = n2;
          n2 = n3;
          if(n3)
          {
             n3 = n3->next;
          }
       }
       while(A)
       {
         if((n1->val)!=(A->val))
         {
            return false;
         }
          A = A->next;
          n1 = n1->next;
       }
       return true;
    }
};

思路二:将链表中的数值存储到数组当中;在进行比较

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) 
    {
        int arr[900] = {0};
        int i = 0;
        while(A)
        {
           arr[i++] = A->val;
           A = A->next;
        }
        int left = 0;
        int right = i-1;
        while(right>left)
        {
          if(arr[right]!=arr[left])
          { 
             return false;
          }
          right--;
          left++;
        }
        return true;
    }
};

思路三: 找中间结点(快慢指针,详情请看第一篇文章),反转以中间结点为头的链表(反转指针,详情看第一篇文章),遍历原链表和以中间节点为头的链表

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A)
    {
       ListNode* fast = A;
       ListNode* slow = A;
       while(fast&&fast->next)
       {
         slow = slow->next;
         fast = fast->next->next;
       }
       ListNode* n1 = NULL;
       ListNode* n2 = slow;
       ListNode* n3 = slow->next;
       while(n2)
       {
          n2->next = n1;
          n1 = n2;
          n2 = n3;
          if(n3)
          n3 = n3->next;
       }
       ListNode* prev = A;
       while(prev!=slow)
       {
          if((prev->val)!=(n1->val))
          return false;
          prev = prev->next;
          n1 = n1->next;
       }
       return true;
    }
};

二、相交链表

2.1 题目

https://leetcode.cn/problems/intersection-of-two-linked-listsicon-default.png?t=O83Ahttps://leetcode.cn/problems/intersection-of-two-linked-lists

2.2 解题思路

因为链表一旦相交那么他们从相交点后的链表一定是一样的,所以链表的长度差只在相交点前,我们先遍历链表找出他们的长度差,然后保证他们遍历时长度是一样的。但他们的下一个节点都是相同的时候相同点就是相交点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode* n1 = headA;
    ListNode* n2 = headB;
    int sizeA = 0;
    int sizeB = 0;
    while(n1)
    {
       sizeA++;
       n1 = n1->next;
    }
     while(n2)
    {
       sizeB++;
       n2 = n2->next;
    }
    int gap = abs(sizeA-sizeB);
    ListNode* longlist = headA;
    ListNode* shortlist = headB;
    if(sizeB>sizeA)
    {
        longlist = headB;
        shortlist = headA;
    }
    while(gap--)
    {
        longlist = longlist->next;
    }
    while(longlist)
    {
        if(longlist==shortlist)
        return longlist;
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    return NULL;
}

标签:表题,单链,ListNode,struct,int,next,链表,n1
From: https://blog.csdn.net/shsbyshdbdhjsk/article/details/143366654

相关文章

  • C语言判断单链表是否相交
    ////CreatedbyAdministratoron2024/10/29.//#ifndefLINK_H#defineLINK_H/***链表的结构体*/typedefstructLink{intelement;structLink*next;}link;#endif//LINK_H////判断单链表是否相交//CreatedbyAdministratoron2024/10/30......
  • 线性表-单链表c语言实现
    一、基本介绍    回顾单链表的知识二、单链表#include<stdio.h> #include<cstdlib>typedefintElemType;typedefintStatus; #defineERROR0#defineOK1#defineOVERFLOW-2#defineNULL0//定义单链表中结点类型 typedefstructLNode{  ......
  • 数据结构-------------二叉树后续(单链表实现二叉树)
    1:前中后序遍历在用链表实现二叉树的时候我们要首先了解一下二叉树的遍历,让我们来看一下二叉树都有那些遍历1.1 遍历规则按照二叉树的遍历规则遍历有:前序.中序.后序。(1)前序:首先访问根节点再去访问左右子树(访问顺序为:根结点、左⼦树......
  • 关于 顺序表、单链表、双链表、栈、队列的小总结
    1.结构的定义方式-顺序表:以结构体指针方式定义-链表:以结构体自引用方式定义-栈:个人推荐使用结构体指针方式定义(类似顺序表)-队列:以结构体指针+结构体自引用方式实现2.对顺序表、单链表、双链表的小小对比顺序表:尾插、尾删操作更方便(对头操作的话需......
  • 【数据结构初阶】单链表接口实现超详解
    1.顺序表问题与思考上一篇博客中我们介绍了顺序表,那么顺序表有什么缺点呢?中间/头部的插入删除,时间复杂度为O(N)增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数......
  • 初阶数据结构【3】--单链表(比顺序表还好的一种数据结构!!!)
    本章概述前情回顾单链表实现单链表彩蛋时刻!!!前情回顾咱们在上一章博客点击:《顺序表》的末尾,提出了一个问题,讲出了顺序表的缺点——有点浪费空间。所以,为了解决这个问题,我们今天就要讲解链表,咱们在讲结构体的时候有提到过链表,链表的最大优点——一点空间也不浪费,用多少......
  • [数据结构] 删除单链表中最小值结点(C语言版本)
    如果对单链表基本操作或概念不理解的可以跳转:单链表的基本操作(C语言版)-CSDN博客https://blog.csdn.net/m0_74181956/article/details/143082621?spm=1001.2014.3001.5501算法思想:如图所示:定义指针p为L的第一个结点,pre为L的头结点,min为记录每次遍历的最小值结点,minpre为记......
  • 单链表的学习和总结
    单链表的学习和总结1.1 反转链表1.1.1 记录leetcode的题目206.反转链表92.反转链表II25.K个一组翻转链表1.1.2整理总结1.记录链表翻转的几种方法:目前我认为“头插法”更好理解https://leetcode.cn/problems/reverse-linked-list/solutions/2948411/dan-lian-......
  • 奇偶序号分割单链表(C语言)
    算法思想:要想将单链表L按照奇偶序号分割为两个单链表A(奇),B(偶),我们便可以定义一个变量来记录当前遍历的结点序号的奇偶,两个指针ra,rb,ra负责将奇数位置结点赋到A中,rb同理核心代码:voiddevide(LinkListL,LinkListA,LinkListB){intindex=1;LNode*p=L->next;......
  • 【C++】原地逆置单链表(不开辟新的储存空间)
    首先看图例:创建一个单链表L,并用指针p指向需要逆置的第一个结点,s指向p的下一个。(这里s的作用是为了防止p后的结点丢失) 第一个结点逆置后成为最后一个,所以其后为NULL,即p->next=NULL(其他结点正常头插)用s指向了的p之后的结点,所以它们不会丢失。第一个结点接上后,p、s重新指向......