永州市规划建设局网站,学会了php的语法怎么做网站,海口网站关键词优化,网站左侧分类导航菜单目录
前言
一、读懂题目
二、思路分析
三、代码呈现
总结 前言 当我们需要访问单向链表中特定位置值时#xff0c;算法复杂度往往是O(n)#xff0c;在得到靠后节点的值时不可避免地从前向后遍历访问链表#xff0c;那么当应题目要求从尾到头打印链表时#xff0c;至少…目录
前言
一、读懂题目
二、思路分析
三、代码呈现
总结 前言 当我们需要访问单向链表中特定位置值时算法复杂度往往是O(n)在得到靠后节点的值时不可避免地从前向后遍历访问链表那么当应题目要求从尾到头打印链表时至少对每个链表节点需要访问两次。那么有哪些方法可以实现题目反向输出地要求呢 一、读懂题目 题目: 输入一个链表的头结点从尾到头反过来打印出每个结点的值 为了便于分析描述我们不妨设定链表节点的定义
typedef struct ListNode
{int val;ListNode* next;
}ListNode;
该题目无论是否使用额外外部空间都可以实现
1当我们不使用额外空间时就必须对链表结构下手由于单链表的遍历都是由前向后所以可以在首次遍历链表时将每个节点间的指针指向关系调转从而接着按照新链表从头到尾打印即可实现题目的倒序打印
2当然一般遍历打印的功能或题目都是更偏向于不希望我们改变原始结构这时就需要额外空间出面解决问题了。我们想到先遍历到的元素后打印和栈的特征完全吻合那么利用栈实现就具有得天独厚的条件。另外同样可以使用数组使用新创建的临时链表都可实现类似的存储功能便于后续依次取出作打印进而解决题目要求。
现在理清可行实现思路后我们进行思路总结和代码呈现
二、思路分析
结合实际需求和功能限制我们全文只讲述不改变原始结构即利用额外空间的方法 1利用栈实现 2利用存值的数组实现比存节点的数组省空间 3利用创建新链表实现 我们需要认识到这三点实现方法中利用栈和新链表的优势在于无需预先知道链表长度节点数目而数组若设定为静态数组局限性很大很容易造成访问越界或空间浪费所以数组需要设定为动态数组且是可以随时根据内部元素size占容量capacity的比值来动态拓展数组空间。换而言之当我们同存储n个节点信息用于打印时数组类型可以仅存每个节点需要打印的数据类型无需存储整个结构体变量当然其他两方法也可以通过存储结构体类型的指针来实现节省空间但是对每个节点元素打印操作前多了一次解引用操作还是会对效率少有影响甚至栈也可设定为打印类型并非结构体指针类型这样可以吸纳数组存储的优点同时避开创建临时新链表的多余解指针操作。 所以接下来我们只讨论只存储打印类型的栈来实现逆序输出的功能剩余两者都是比较好实现的可以通过栈来对照模拟。
三、代码呈现
首先给出简单单链表这里需要用到的基础函数
// 链表基础功能
ListNode* init_List()
{ListNode* head new ListNode();if (head nullptr) { return nullptr; }head-val 0;head-next nullptr;
}ListNode* appendNode(ListNode* head, int val)
{assert(head);ListNode* node new ListNode();node-val val;node-next nullptr;ListNode* cur head;while (cur-next ! nullptr){cur cur-next;}cur-next node;return node;
}void printList(const ListNode* head) // 注意这里直接设定为const ListNode*
{assert(head);const ListNode* cur head-next;while (cur ! nullptr){printf(%-8d, cur-val);cur cur-next;}printf(\n);
}
接着我们构建一个简单链表
ListNode* test_list()
{ListNode* head init_List(); // 带头节点的单链表appendNode(head, 10);appendNode(head, 9);appendNode(head, 8);appendNode(head, 7);appendNode(head, 6);return head;
}
利用栈实现逆序打印
void test1()
{// 打印正序对比ListNode* head test_list();printf(正序打印);printList(head);// 遍历并将节点用于打印的值填入栈内const ListNode* cur head-next;stackint st;while (cur ! nullptr){st.push(cur-val);cur cur-next;}// 对栈遍历打印printf(逆序打印);while (!st.empty()){printf(%-8d, st.top());st.pop();}printf(\n);
}
运行结果 可以看到结果很理想同时我们没有在首次遍历链表时使用计数器统计节点个数。
我们想到栈和递归实际上是一回事那可不可以写出对应的利用递归实现的功能代码呢
利用递归实现逆序打印
// 利用递归实现
void traversal_back_printList(const ListNode* node)
{if (node nullptr) { return; }static const ListNode* const index node; // 很重要 通过index标记链表头节点的地址避免打印其初始化val值0traversal_back_printList(node-next);if (node ! index){printf(%-8d, node-val);}else{printf(\n);}
}
需要注意的是语句 “static const ListNode* const index node;” 中static用于保证递归过程中每次进入函数都不会改变index存储的是头结点所在地址的值避免后续执行递归函数最外层时打印头结点初始化的值第一个const用于等价接收cosnt ListNode* node节点第二个const在这里可省略。
运行结果 总结
在单向链表中要实现逆序打印链表的要求可以采用以下几种方法 利用栈遍历链表将节点的值依次压入栈中然后再依次弹出栈顶元素即可实现逆序打印链表的效果。这种方法不需要改变链表的结构适用于不知道链表长度的情况。 利用递归通过递归的方式先递归访问链表的后续节点再打印当前节点的值可以实现逆序打印链表。需要在递归函数中设置一个标记来避免打印头节点的初始化值。 利用新链表New List或数组Array遍历链表将节点的值存储到新链表或数组中然后按照逆序从新链表或数组中取出并打印节点的值。这种方法需要额外的空间来存储节点的值适用于不想改变链表结构的情况。
需要注意的是以上三种方法都可以实现逆序打印链表的功能选择使用哪种方法取决于具体的需求和限制。根据题目要求或实际情况选择最合适的方法来实现。
