摘要:導航小助手劍指從尾到頭打印鏈表題目詳情解題思路源代碼總結劍指從尾到頭打印鏈表題目詳情輸入一個鏈表的頭節點,從尾到頭反過來返回每個節點的值用數組返回。時間復雜度方法先反轉鏈表并求長度,在將反轉后的鏈表數據拷貝至數組中。
??前面的話??
大家好!博主開辟了一個新的專欄——劍指offer,我要開始刷題了!這個專欄會介紹《劍指offer》書上所有的面試編程題。并且會分享一些我的刷題心得。由于博主水平有限,如有錯誤,歡迎指正,如果有更好的解題思路和算法可以分享給博主哦!一起加油!一起努力!
?博客主頁:未見花聞的博客主頁
?歡迎關注?點贊?收藏??留言?
?本文由未見花聞原創,CSDN首發!
?首發時間:?2021年9月3日?
??堅持和努力一定能換來詩與遠方!
?參考書籍:?《劍指offer第1版》,?《劍指offer第2版》
?參考在線編程網站:?牛客網?力扣
?作者水平很有限,如果發現錯誤,一定要及時告知作者哦!感謝感謝!
博主的碼云gitee,平常博主寫的程序代碼都在里面。
輸入一個鏈表的頭節點,從尾到頭反過來返回每個節點的值(用數組返回)。
示例:
輸入:head = [1,3,2]輸出:[2,3,1]
限制:
0 <= 鏈表長度 <= 10000
來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
方法1: 先求鏈表長度,然后再將鏈表中的元素逆序存入數組中。
時間復雜度: O(N)
方法2: 先反轉鏈表并求長度,在將反轉后的鏈表數據拷貝至數組中。
反轉鏈表方法見劍指offer系列——劍指 Offer 24. 反轉鏈表(C語言)
時間復雜度: O(N)
編程語言:C語言
在線編程平臺:力扣
//方法1/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; *//** * Note: The returned array must be malloced, assume caller calls free(). */int* reversePrint(struct ListNode* head, int* returnSize){ int cnt = 0; struct ListNode* cur = NULL; cur = head; while(cur) { cnt++; cur = cur->next;//求鏈表中元素個數 } int* arr = (int*)malloc(sizeof(int)*cnt);//分配給數組合適的空間 *returnSize = cnt; cur = head; while(cur) { *(arr + cnt - 1) = cur->val;//將鏈表的元素逆向存入數組中 cur = cur->next; cnt--; } return arr;}
//方法2int* reversePrint(struct ListNode* head, int* returnSize){ if (head == NULL) { *returnSize = 0; return NULL; } int cnt = 0;//記錄元素個數 struct ListNode* cur = head; struct ListNode* next = NULL; struct ListNode* tail = NULL; while (cur) { next = cur->next; cur->next = tail; tail = cur; cur = next; cnt++; }//反轉鏈表并求鏈表長度 int* arr = (int*)malloc(sizeof(int)*cnt); *returnSize = cnt; cur = tail; int i = 0; for (i = 0; i < cnt; i++) { arr[i] = cur->val; cur = cur->next; } return arr;}
對于鏈表的逆序打印,可以先統計鏈表元素個數,然后根據鏈表元素個數創建合適大小的數組,最后再將鏈表中的元素逆序存入數組中!還可以先進行反轉鏈表并求出鏈表元素個數,同理根據鏈表大小為數組申請空間,最后將反轉鏈表中的元素存入數組中!
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/119110.html
摘要:題目輸入一個鏈表的頭節點,從尾到頭反過來返回每個節點的值用數組返回。 題目輸入一個鏈表的頭節點,從尾到頭反過來返回每個節點的值(用數組返回)。示例 1:輸入:head = [1,3,2]輸出:[2,3,1]限制:0
摘要:題目描述輸入一個鏈表,按鏈表值從尾到頭的順序返回一個。最后別忘了,從尾到頭遍歷鏈表,不要忘了將你的結果進行翻轉。 題目描述 輸入一個鏈表,按鏈表值從尾到頭的順序返回一個ArrayList。 分析 要了解鏈表的數據結構: val屬性存儲當前的值,next屬性存儲下一個節點的引用。 要遍歷鏈表就是不斷找到當前節點的next節點,當next節點是null時,說明是最后一個節點,停止遍歷。 最...
題目 輸入一個鏈表的頭節點,從尾到頭反過來打印出每個節點的值。 解題思路 一、棧 第一個遍歷的節點最后一個輸出,而最后一個比遍歷到的節點第一個輸出(后進先) public static ArrayList printListFromTailToHead(ListNode listNode){ ArrayList list = new ArrayList(); ...
摘要:劍指中鏈表相關題目俗話說光說不練假把式,既然學習了鏈表的基礎概念和基本操作那我們一定要找些題目鞏固下,下面來看劍指中的相關題目。題目分析合并兩個排序的鏈表,需要分別比較兩個鏈表的每個值,然后改變指針。 溫故知新 鏈表由一個一個的作為節點的對象構成的,每一個節點都有指向下一個節點的指針,最后一個節點的指針域指向空。每個節點可以存儲任何數據類型。 根據類型可以分為單鏈表、雙鏈表、環形鏈表、...
摘要:一定要認真看分析注釋題目要求題目描述輸入一個鏈表,從尾到頭打印鏈表每個節點的值。分析因為鏈表只有知道當前結點才能知道下一結點,所以不可能直接從后往前打印。 一定要認真看 分析 | 注釋 | 題目要求 Question 1 題目描述:輸入一個鏈表,從尾到頭打印鏈表每個節點的值。 分析:因為鏈表只有知道當前結點才能知道下一結點,所以不可能直接從后往前打印。這種逆序的算法(策略)我們常用棧這...
閱讀 2101·2021-11-18 10:02
閱讀 2850·2021-09-04 16:41
閱讀 1142·2019-08-30 15:55
閱讀 1405·2019-08-29 17:27
閱讀 1068·2019-08-29 17:12
閱讀 2534·2019-08-29 15:38
閱讀 2853·2019-08-29 13:02
閱讀 2829·2019-08-29 12:29