【Leetcode】重排链表、旋转链表、反转链表||

这篇具有很好参考价值的文章主要介绍了【Leetcode】重排链表、旋转链表、反转链表||。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

💡重排链表

题目描述

方法一:

方法二:

💡旋转链表

题目描述

方法:

💡反转链表||

题目描述

方法:

💡总结


【Leetcode】重排链表、旋转链表、反转链表||,数据结构,leetcode,链表,算法,c语言

💡重排链表

题目描述

给定一个单链表 L 的头节点 head ,单链表 L 表示为:

 L0 → L1 → … → Ln-1 → Ln 
请将其重新排列后变为:

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

提示:

  • 链表的长度范围为 [1, 5 * 104]
  • 1 <= node.val <= 1000

【Leetcode】重排链表、旋转链表、反转链表||,数据结构,leetcode,链表,算法,c语言

方法一:

将链表的每一个节点存在数组里,然后用下标访问的方式,交叉连接。

【Leetcode】重排链表、旋转链表、反转链表||,数据结构,leetcode,链表,算法,c语言

【Leetcode】重排链表、旋转链表、反转链表||,数据结构,leetcode,链表,算法,c语言

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;
void reorderList(struct ListNode* head){
    if(head->next==NULL||head->next->next==NULL)
    return;
    ListNode* arr[50001];
    ListNode* cur=head;
    int n=0;
    while(cur)
    {
        arr[n]=cur;
        cur=cur->next;
        n++;
    }
    int i=0;
    int j=n-1;
    while(i<j)
    {
        arr[i]->next=arr[j];
        i++;
        
        arr[j]->next=arr[i];
        j--;
    }
        arr[i]->next=NULL;

}

方法二:

可以先用快慢指针的方法找到链表的中间节点,然后将中点后的链表翻转成一个新的链表,最后将这个新链表和原链表切割掉中间节点之后的链表合并成一个新的链表,合并方式是交叉合并。

【Leetcode】重排链表、旋转链表、反转链表||,数据结构,leetcode,链表,算法,c语言

【Leetcode】重排链表、旋转链表、反转链表||,数据结构,leetcode,链表,算法,c语言

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;
ListNode* MiddleNode(ListNode* head)
{
    ListNode* fast=head;
    ListNode* slow=head;
    while(fast!=NULL&&fast->next!=NULL)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}
ListNode* ReverseList(ListNode* head)
{
    ListNode* phead=NULL;
    ListNode* cur=head;
    while(cur)
    {
        ListNode* tmp=cur->next;//注意先后顺序
        cur->next=phead;
        phead=cur;
        cur=tmp;
    }
    return phead;
}
void reorderList(struct ListNode* head){
    ListNode* mid=MiddleNode(head);
    ListNode* phead=ReverseList(mid->next);
    mid->next=NULL;
    ListNode* cur=head;
    while(phead)
    {
        ListNode* next=cur->next;
        cur->next=phead;
        ListNode* tmp= phead->next;
        phead->next=next;
        phead=tmp;
        cur=cur->next->next;
    }

}

💡旋转链表

题目描述

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。

提示:

  • 链表中节点的数目在范围 [0, 500] 内
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 109

【Leetcode】重排链表、旋转链表、反转链表||,数据结构,leetcode,链表,算法,c语言

方法:

要求每个节点向右移动k位置,其实就是将倒数k个结点接在头节点之前,倒数第k个结点成为新的头节点,但是这里需要对k进行处理,因为k可能大于链表长度,所以k=k%len,还有一个需要注意的就是当k==len时,是不需要进行任何操作的,直接返回头节点就可以了。

【Leetcode】重排链表、旋转链表、反转链表||,数据结构,leetcode,链表,算法,c语言

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* rotateRight(struct ListNode* head, int k) {
    if(head==NULL||k==0)
    return head;
    ListNode* cur=head;
    ListNode* prev=head;
    ListNode* ret=head;
    int l=0;
    while(ret)
    {
        ret=ret->next;
        l++;
    }
    k=k%l;
    if(k==0)
    return head;
    while(k--)
    {
        cur=cur->next;
    }
    while(cur->next)
    {
        cur=cur->next;
        prev=prev->next;
    }

    ListNode*  Next=prev->next;
    cur->next=head;
    prev->next=NULL;
    return Next;
}

💡反转链表||

题目描述

给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

提示:

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

【Leetcode】重排链表、旋转链表、反转链表||,数据结构,leetcode,链表,算法,c语言

方法:

我的方法就是将区间[left,right]之间的结点翻转,然后与原来区间前后的结点重新连接起来。

【Leetcode】重排链表、旋转链表、反转链表||,数据结构,leetcode,链表,算法,c语言

【Leetcode】重排链表、旋转链表、反转链表||,数据结构,leetcode,链表,算法,c语言

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head,struct ListNode* tail)
{
    ListNode*phead=NULL;//新的头
    ListNode*cur=head;
    while(cur!=tail)//遍历原链表
    {
        ListNode*next=cur->next;//保存下一个节点的地址,避免丢失
        cur->next=phead;
        phead=cur;//更新头节点
        cur=next;//继续遍历
    }
    return phead;
}
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    ListNode* cur1=head;
    ListNode* cur2=head;
    int cnt=1;
    while(cnt<left-1)
    {
        cur1=cur1->next;
        cur2=cur2->next;
        cnt++;
    }
    while(cnt<=right)
    {
        cur2=cur2->next;
        cnt++;
    }
    ListNode* tail=NULL;               
    if(cur2!=NULL)
        tail=cur2;
    if(left==1)
    head=reverseList(cur1,cur2);
    else
    cur1->next=reverseList(cur1->next,cur2);
    while(cur1->next)
    {
        cur1=cur1->next;
    }
    cur1->next=tail;

    return head;
}

💡总结

链表相关的题目还是要注意细节,结点之间的切割与连接要特别仔细,不然任意造成空结点,或者成环导致死循环。文章来源地址https://www.toymoban.com/news/detail-775590.html

到了这里,关于【Leetcode】重排链表、旋转链表、反转链表||的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法分析】反转链表与顺序表(内含源码,思路清晰)

      顺序表和链表都是数据结构中常见的线性表。它们的主要区别在于 内存管理方式不同 。   顺序表(Array)是由一系列元素按照一定顺序依次排列而成,它使用连续的内存空间存储数据。顺序表使用一个数组来存储数据,数组中的每个元素都可以通过下标来访问。顺序

    2024年02月07日
    浏览(101)
  • 【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析)

    还不清楚链表的码喵们可以看看前篇关于链表的详解 既然已经懂得了链表该如何实现,那么现在就趁热打铁开始练习!这里给码喵们整理了相对不错的一些OJ题来练习  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 思路:遍历整个表,访问每个表的值并且删除再将nex

    2024年02月22日
    浏览(48)
  • 第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)

    1、前序、中序、后序遍历 分析: 完全二叉树: 叶结点只能出现在最底层的两层,且最底层叶结点均处于次底层叶结点的左侧 2、线性结构 3、其它 4、单向链表构建 (1)定义一个单向链表SingleLinked类 包含私有的静态内部类Node 包含Object类型的data属性和Node类型的next属性 包含

    2024年01月23日
    浏览(48)
  • LeetCode 刷题 数据结构 链表 203 移除链表元素

    Given the  head  of a linked list and an integer  val , remove all the nodes of the linked list that has  Node.val == val , and return  the new head . Example 1: Example 2: Example 3: Constraints: The number of nodes in the list is in the range  [0, 104] . 1 = Node.val = 50 0 = val = 50 今天leetcode的中文官网比较卡,所以是登录官网进行

    2024年02月14日
    浏览(33)
  • 【数据结构 | 链表】leetcode 2. 两数相加

    个人主页:兜里游客棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里游客棉花糖 原创 收录于专栏【LeetCode】 原题链接:点击直接跳转到该题目 给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位

    2024年02月05日
    浏览(52)
  • 【LeetCode】数据结构题解(5)[分割链表]

    所属专栏:玩转数据结构题型 博主首页:初阳785 代码托管:chuyang785 感谢大家的支持,您的点赞和关注是对我最大的支持!!! 博主也会更加的努力,创作出更优质的博文!! 关注我,关注我,关注我,重要的事情说三遍!!!!!!!! 分割链表 给你一个链表的头节点

    2024年02月04日
    浏览(48)
  • 【LeetCode】数据结构题解(6)[回文链表]

    所属专栏:玩转数据结构题型 博主首页:初阳785 代码托管:chuyang785 感谢大家的支持,您的点赞和关注是对我最大的支持!!! 博主也会更加的努力,创作出更优质的博文!! 关注我,关注我,关注我,重要的事情说三遍!!!!!!!! 回文链表 给定一个链表的 头节点

    2024年02月03日
    浏览(46)
  • 【Leetcode】反转链表 合并链表 相交链表 链表的回文结构

      目录 一.【Leetcode206】反转链表 1.链接 2.题目再现  3.解法A:三指针法 二.【Leetcode21】合并两个有序链表 1.链接 2.题目再现  3.三指针尾插法 三.【Leetcode160】相交链表 1.链接 2.题目再现 3.解法 四.链表的回文结构 1.链接 2.题目再现  3.解法 1.链接 反转链表 2.题目再现  3.解法

    2024年02月02日
    浏览(48)
  • 数据结构与算法之字符串: Leetcode 557. 反转字符串中的单词 III (Typescript版)

    翻转字符串中的单词 III https://leetcode.cn/problems/reverse-words-in-a-string-iii/ 描述 给定一个字符串 s ,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 示例 1: 示例 2: 提示: 1 = s.length = 5 * 1 0 4 10^4 1 0 4 s 包含可打印的 ASCII 字符。 s 不包含任何开头或

    2024年02月01日
    浏览(74)
  • 【数据结构】[LeetCode138. 复制带随机指针的链表]

    给你一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random  ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的  深拷贝 。 深拷贝应该正好由  n  个  全新  节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的  next  指针和

    2024年02月04日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包