首页 > C语言的单链表逆序和指定范围逆序

C语言的单链表逆序和指定范围逆序

文章目录

          • 前言
          • 逆序
          • 指定范围逆序
          • 源码实现

前言

关于链表的逆置，是考察对链表指针的理解。知道了如何不实用额外空间，同时使用O(n)复杂度对链表进行逆序之后将会对链表有好理解。

同时关于如何在指定范围内对链表逆置同样可以进一步加深理解

逆序

基本过程如下：

  1. 保留原始链表的next指针域,p = head -> next
  2. 将原始链表的next指针域指向新链表的头部,head -> next = new_head
  3. 新链表指针向前移动一位,new_head = head
  4. 原始链表头指针向后移动一位，指向之前保留的原始指针的next域，head = p

在这里插入图片描述

在这里插入图片描述

···

在这里插入图片描述

以上过程实现如下:

Data *reverse(Data *head) { Data *new_head = NULL;while(head) { Data *p = head -> next;head -> next = new_head;new_head = head;head = p;}return new_head;
}
指定范围逆序

基本过程如下，指定链表的第2-4个节点进行逆序，其他节点保持原有顺序

在这里插入图片描述

这个过程需要关注如下几个关键节点

在这里插入图片描述

  1. 逆序前的头节点和逆序后的尾节点需要确认，确认之后在此范围即可进行如上过程的链表逆序
  2. 逆序完成之后需要连接头节点
  3. 逆序完成之后需要连接尾节点

实现过程如下:

/*指定范围，逆序m-n之间的节点*/
Data *reverse_betweenM_N(Data *head, int m, int n) { Data *result, new_tail;Data *new_head = NULL;Data *pre_head = NULL;/*计算需要逆序的节点个数，从而能够找到逆序的尾节点*/int change = n - m + 1;/*跳过m个节点，找到逆序前的第一个节点*/result = head;while(head && --m) { pre_head = head;head = head -> next;}/*保留逆序前的第一个节点，逆序后将变为尾节点*/Data *list_tail = head;/*逆序m-n之间的节点*/while(head && change) { Data *p = head -> next;head -> next = new_head;new_head = head;head = p;change --;}/*逆序完成之后，将逆序后的尾节点指向链表结尾*/list_tail -> next = head;/*确认逆序节点不是从链表头节点开始：如果是则最终头节点为逆序后的头节点否则将头节点指向逆序后的头节点，保持链表完成性*/if (pre_head) { pre_head -> next = new_head;result = pre_head;} else { result = new_head;}return result;
}
源码实现
#include 
#include /*链表数据域和指针域*/
typedef struct link_list { int data;struct link_list *next;
}Data;/*打印链表*/
void print_list(Data *head) { while (head) { printf("%d ",head->data);head = head -> next;}printf("
");
}/*头插法创建链表*/
Data *insert_head(Data *head, int n) { head = (Data *)malloc (sizeof(Data));head -> next = NULL;int data;while(n --) { Data *p = (Data *)malloc(sizeof(Data));scanf("%d",&data);p -> data = data;p -> next = head -> next;head -> next = p;}return head;
}/*尾插法创建链表*/
Data *insert_tail(Data *head, int n) { head = (Data *)malloc(sizeof(Data));head -> next = NULL;Data *r = head;int data;while(n--) { Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &data);p -> data = data;r -> next = p;r = p;p -> next = NULL;}return head;
}/*链表逆序*/
Data *reverse(Data *head) { Data *new_head = NULL;while(head) { Data *p = head -> next;head -> next = new_head;new_head = head;head = p;}return new_head;
}/*链表指定范围逆序*/
Data *reverse_betweenM_N(Data *head, int m, int n) { Data *result, new_tail;Data *new_head = NULL;Data *pre_head = NULL;int change = n - m + 1;result = head;while(head && --m) { pre_head = head;head = head -> next;}Data *list_tail = head;while(head && change) { Data *p = head -> next;head -> next = new_head;new_head = head;head = p;change --;}list_tail -> next = head;if (pre_head) { pre_head -> next = new_head;result = pre_head;} else { result = new_head;}return result;
}int main() { Data *head;printf("construct link list :
");head = insert_tail(head,5);Data *test = reverse_betweenM_N(head -> next,2,4);printf("after reverse between 2-4:
");print_list(test);Data *rever = reverse(head -> next);printf("after reverse :
");print_list(rever);return 0;
}

输出如下:

construct link list :
1 2 3 4 5
after reverse between 2-4:
1 4 3 2 5 
after reverse :
5 2 3 4 1

更多相关：

  • 剑指offer：面试题35. 复杂链表的复制

    题目：复杂链表的复制 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 示例 1： 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出...

  • leetcode-86 分隔链表

    给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 使用双指针的方式，各自构造一个大元素的头节点和小元素...

  • leetcode-142 环形链表II

    给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 示例 1： 输入：head = [3,2,0,-4], pos = 1...

  • leetcode-92 反转链表II

    题目描述如下： 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL 很明显这个题目是206 反转链表的进阶版 需要记录第m-1个节点和第n+1个...

  • leetcode-206 反转链表

    描述如下： 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 方法一：原地反转 数据结构如下 struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}...

  • python制作统计图_刻意练习11：Python描述统计、简单统计图形

    学习计划 MyPlan11 主题：Python描述统计、简单统计图形 时间：8.5-8.11周内完成 参考资料：新书《谁说菜鸟不会数据分析python篇》 各位星友们，在这个星球里每个人都要逼迫自己学习未知的领域或知识点，每天进步一点点，积累的时间久了 ，菜鸟也能起飞。 完成情况： 在pandas中，使用describe函数进行描述统...

  • python3socket非阻塞_利用Python中SocketServer 实现客户端与服务器间非阻塞通信

    利用SocketServer模块来实现网络客户端与服务器并发连接非阻塞通信。 首先，先了解下SocketServer模块中可供使用的类： BaseServer：包含服务器的核心功能与混合（mix-in）类挂钩；这个类只用于派生，所以不会生成这个类的实例；可以考虑使用TCPServer和UDPServer。 TCPServer/UDPS...

  • 剑指offer：面试题37. 序列化二叉树

    题目：序列化二叉树 请实现两个函数，分别用来序列化和反序列化二叉树。 示例:  你可以将以下二叉树：     1    /   2   3      /     4   5 序列化为 "[1,2,3,null,null,4,5]" 解题： /*** Definition for a binary tree no...

  • sd.js 2.0封装：更加简化请求传参内容

    sd.js  import $global from "./global"; import $g from "./sg"; import $ from "jquery"; import {Message, Loading} from "element-ui";//引入饿了么相关组件 import {Base64} from "js-...

  • sd.js帮助您简化繁重的获取数据、存储数据（CRUD）骚操作（吐槽~在安卓9.0以下或者IOS10.X以下手机端H5页面不支持，在这两

        原生sd.js----------------------------------------------------------------  const API_ROOT_URL = "http://www.api.com";const $d= {_postList_url: API_ROOT_URL + "/api...

  • 剑指offer：面试题25. 合并两个排序的链表

    题目：合并两个排序的链表 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 限制： 0 <= 链表长度 <= 1000 解题: /*** Definition for singly-linked li...

  • 剑指offer：面试题24. 反转链表

    题目：反转链表 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 限制： 0 <= 节点个数 <= 5000 解题： 方法一：双指针 我们可以申请两个指针，第一个指针叫 new_next，最...

  • LRU算法 -- 链表 完整实现

    LRU算法(Least Recently Used) 算是我们经常遇到的一种淘汰算法，其中内存管理模块进行内存页回收时有用到，针对不经常使用的内存页，LRU淘汰策略能够将该内存页回收给操作系统。 属于 我们操作系统设计中的 时间局部性原理，最长时间未被访问的数据优先淘汰，当内存中已存在的数据再次被访问时，则进行热度的提升。 本文为...

  • leetcode-24 两两交换链表中的节点

    题目描述 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例: 给定 1->2->3->4, 你应该返回 2->1->4->3. 方法一（递归）： 将配对交换过程拆解为多个以两个元素为一对的子问题 …n(k-1) -> n(k)->n(k+1)...

  • C语言的有序单链表合并

    已知两个已排序链表头节点指针headA与headB，将这两个链表合并，合并后仍为 有序的，返回合并后的头节点。 主要步骤如下： 创建一个临时的头节点，头节点每次指向headA 或者 headB较小的节点当headA->data 比headB->data小的时候，headA的当前节点加入临时头节点，同时headA指针向后移动；否则h...

©2024 11GX.COM