代码编织梦想

复试算法练习Day17——从头到尾打印链表

题目描述

输入一个链表的头节点,按链表从尾到头的顺序返回每个节点的值(用数组返回)。

如输入{1,2,3}的链表如下图:

img

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000

示例1

输入:

{1,2,3}

返回值:

[3,2,1]

示例2

输入:

{67,0,24,58}

返回值:

[58,24,0,67]

思路

思路一:虽然从头到尾输出比较简单,但是如果需要从尾到头打印链表,最好的方法就是直接把链表中的结点指针翻转过来,改变链表方向,就可以从头到尾输出,但是这样会改变链表数据结构。因此,可以考虑直接从头到尾输出数据后,把数据依次入栈,然后从栈中输出结果,这样就可以得到从尾到头的链表在数组中输出的结果了。

思路二:利用两个数组,首先建立链表然后把链表的数据输出到第一个数组,统计数组长度,然后利用两个相同的长度的数组,来互相首尾互换给出反转后的数据结果,输出即可得到从尾到头的数组。

具体实现

//利用栈FILO的原理,在不破坏链表结构的条件下,
//利用数组从尾到头逆序输出数据
#include <stdio.h>
#include <stdlib.h>
//链表初始化 
typedef struct _list{
	struct _list *next;
	int data;
}List;
//数据栈初始化
typedef struct _stack{
	int data[10];
	int top;
}Stack;
//入栈函数
int InitStack(Stack *s){
	if(s == NULL){
		return 0;
	}
	s->top = -1;
	
	return 1;
}
//链表插入函数
int Insert_list(List *list, int data){
	//如果链表为空,返回0
    if(list == NULL){
		return 0;
	}
	//否则开辟空间存放链表指针和链表节点
	List *node = (List *)malloc(sizeof(List)/sizeof(char));
	//如果节点为空,则返回0
	if(node == NULL){
		return 0;
	}
	//利用尾插法插入节点,并插入数据
	node->data = data;
	node->next = list->next;
	list->next = node;
	//结束后返回1
	return 1;
}
//利用栈打印链表元素
int Display(Stack *s, List *list) {
	//在栈指针为空且链表节点为空,输出0
    if(s == NULL || list == NULL){
		return 0;
	}
	//将链表数据依次入栈
	List *tmp = list->next;
	while(tmp){
		s->data[++s->top] = tmp->data;
		tmp = tmp->next;
	}
    //当栈满后,依次输出栈底元素
	while(s->top != -1){
		printf("%4d",s->data[s->top--]);
	}
	printf("\n");
	return 1;
}

 //递归打印链表元素
void r_display(List *list){
	//如果链表为空输出0
    if(list->next == NULL){
		return  0;
	}
    //否则多次递归输出节点内容   
	r_display(list->next);
	printf("%4d",list->next->data);
}
 
int main(){
    //栈空间初始化
	Stack *s = (Stack *)malloc(sizeof(Stack)/sizeof(char));
	if(s == NULL){
		return 0;
	}
    //置空栈
	InitStack(s);
	
    //链表空间初始化
	List *list = (List *)malloc(sizeof(List)/sizeof(char));
	if(list == NULL){
		return 0;
	}
	list->next = NULL;
    
    //链表头插法输入元素,后输入
	Insert_list(list,1);
	Insert_list(list,2);
	Insert_list(list,3);
	Insert_list(list,4);
	Insert_list(list,5);
	Insert_list(list,6);
	Insert_list(list,7);
	r_display(list);
	printf("\n");
	//Display(s,list);
	
	return 0;
}
 
 

//注意返回值必须初始化地址之后,才可以将链表节点释放
/**定义链表结构体
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//建立反向输出函数后递归调用
int* reversePrint(struct ListNode* head, int* returnSize){
    //如果链表为空
    if(NULL == head){
        //返回值指针为0
        * returnSize = 0;
        return NULL;
    }
    
    //设置头结点指针
    struct ListNode *p = head;
    int count = 0;
    int i = 0;
    
    //数组空间初始化
    int* temp = (int*)malloc(sizeof(int) * 10000);
    int* res = (int*)malloc(sizeof(int) * 10000);
    //依次出入链表中数据
    while(NULL != p->next){
        temp[count] = p->val;  
        count++;  
        p = p->next;    
    }
    //数组内容计数
    temp[count] = p->val;
    count++;

    *returnSize = count;
    
    //将数组反转后调整内容对应输出
    for(i = 0;i < count;i++){
        res[i] = temp[count - 1 - i];
    }
    return res;
}

时间复杂度

对于方案一,采用栈的方法FILO输出,遍历一次即可,时间复杂度为O(n),设置栈空间与数组空间因此可以给出,本算法的空间复杂度为O(n)

对于方案二,采用建立两个数组的方法,输入一次链表内容时间复杂度为O(n),建立两个数组得到数组长度反转则其空间复杂度为O(n)

小结

总结:如果每次只考虑打印输出一个节点的值,那么这样的时间复杂度会为O(n^2),所以这种方法是不可取的。进而可以考虑采用栈这种数据类型就是先进后出,与题目中要求不谋而合,所以采用栈的方式去打印链表,利用递归方法,这样可以使你的代码变得很简洁,或者采用方法二,利用数组知道长度可以反转数组的特性,先顺序输出内容,后采用两个相同长度数组反转数组内容就可以得到从尾到头输出的链表中的数据,且数据保存在数组中,这种方法极大的考虑到了数组的用法,但是如果数组内容过大,其运算结果也会变慢,需要灵活处理。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44068654/article/details/128859780

算法导论 xor双向循环链表——内存高效链表-爱代码爱编程

XOR双向循环链表——内存高效链表 1. 算法导论原题 10.2-8 ★(★代表题目略有难度) Explain how to implement doubly linked lists using only on

有趣的数据结构算法7——双向循环链表的实例应用_bubbliiiing的博客-爱代码爱编程

有趣的数据结构算法7——双向循环链表的实例应用 问题复述解题思路实现代码GITHUB下载连接 问题复述 要求实现用户输入一个数字改变26个字母的排列顺序。正常情况下26个字母的排列顺序是A B C D E F

数据结构与算法实验报告——实验一 链表-爱代码爱编程

实验一 链表 实验目的和要求 1.理解线性表的链式存储结构。 2.熟练掌握动态链表结构及有关算法的设计。 根据具体问题的需要,设计出合理的表示数据的链表结构,并设计相关 算法。 实验任务 1. 对任意输入的一组数据,建立一个递增有序的单链表。 2. 将单链表L中的奇数项和偶数项结点分解开,并分别连成一个单链表。 3. 用递增有序的链表A、B表示两个集合

【算法练习】81.移除重复节点——链表-爱代码爱编程

⭐加入组队刷题,每日一题,每天进步⭐ 不用缓冲区,就需要首先对链表元素进行排序,并且需要采用稳定排序算法保证等值节点的相对顺序。排序后即可进行去重处理。 ——leetcode此题热评 前言 哈喽,大家好,我是一条。 糊涂算法,难得糊涂 点击跳转到《糊涂算法》专栏学习java大厂面试必备数据结构和算法知识! Question 面试

【数据结构与算法】—— * 链表 入门(三)*-爱代码爱编程

前言 之前,小玄已经写过了链表相关的文章: 【数据结构与算法】—— * 链表 入门(一)*_forever_bryant的博客-CSDN博客 【数据结构与算法】—— * 链表 入门(二)*_forever_bryant的博客-CSDN博客 在这篇文章,小玄将通过实例讲解的方式来为大家进一步温习相关的内容和知识点。 基本概念

js算法——实现反转链表-爱代码爱编程

题 题目来自leetcode。 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL /** * Definition for singly-linked list. *

Python数据结构与算法(2.6)——块状链表-爱代码爱编程

Python数据结构与算法(2.6)——块状链表 0. 学习目标 1. 块状链表简介 1.1 块状链表介绍 1.2 块状链表中结点类 1.3 块状链表中块类 2. 块状链表的实现 2.1 块状链表的初始化 2.2 获取块状链表的长度

C语言数据结构篇——单循环链表的创建,插入,节点删除,打印等操作-爱代码爱编程

目录 初识循环链表 循环链表头结点和数据节点的定义 循环链表的创建  循环链表数据节点的插入  循环链表数据节点的删除 循环链表的遍历打印  完整代码  初识循环链表 在学习过单链表以及进阶的双链表之后就需要进一步学习循环链表了,顾名思义,这种链表头尾相接,形成一个环(即尾节点的后继指针指向第一个节点),其他的单链表的差别不大,但循环

leetcode(python)—— 删除排序链表中的重复元素(简单)_娱乐不打烊丶的博客-爱代码爱编程

删除排序链表中的重复元素 概述:给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 输入:head = [1,1,2] 输出:[1,2] 输入:head = [1,1,2,3,3] 输出:[1,2,3] 方法一:遍历 思路:我们从指针 tem 指向链表的头节点,随后开始对链表进行遍历。如果

剑指offer(python)—— 从尾到头打印链表(简单)_娱乐不打烊丶的博客-爱代码爱编程

从尾到头打印链表 概述:输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。 输入:head = [1,3,2] 输出:[2,3,1] 方法一:递归 思路:先走至链表末端,回溯时依次将节点值加入列表 ,这样就可以实现链表值的倒序输出。 # 递归 class Solution: def reversePrint(self,

python数据结构与算法(2.3)——链表_python链表数据结构 盼小辉-爱代码爱编程

Python数据结构与算法(2.3)——链表 0. 学习目标 1. 线性表的链式存储结构 1.1 指针相关概念 1.2 指

python数据结构与算法(2.4)——双向链表_数据结构与算法python:双链表的操作实现-爱代码爱编程

Python数据结构与算法(2.4)——双向链表 0. 学习目标 1. 双向链表简介 1.1 双向链表介绍 1.2 双向链表结点类

c++基础知识——stl之链表_stl链表-爱代码爱编程

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、什么是链表二、链表的分类顺序链表链表结构图 2.逆序链表 链表的库函数(模板函数)STL之list的