資訊專欄INFORMATION COLUMN
摘要：假設反轉對象節點為，反轉指向的結點為，反轉后指向的結點為首結點。當然也可以根據棧先進后出的特點，使用棧反轉鏈表。
??前面的話??
大家好！博主開辟了一個新的專欄——劍指offer，我要開始刷題了！這個專欄會介紹《劍指offer》書上所有的面試編程題。并且會分享一些我的刷題心得。由于博主水平有限，如有錯誤，歡迎指正，如果有更好的解題思路和算法可以分享給博主哦！一起加油！一起努力！
?博客主頁：未見花聞的博客主頁
?歡迎關注?點贊?收藏??留言?
?本文由未見花聞原創，CSDN首發！
?首發時間：?2021年9月2日?
??堅持和努力一定能換來詩與遠方！
?參考書籍：?《劍指offer第1版》，?《劍指offer第2版》
?參考在線編程網站：?牛客網?力扣
?作者水平很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！
博主的碼云gitee，平常博主寫的程序代碼都在里面。
定義一個函數，輸入一個鏈表的頭節點，反轉該鏈表并輸出反轉后鏈表的頭節點。
示例：
輸入: 1->2->3->4->5->NULL輸出: 5->4->3->2->1->NULL限制：
0 <= 節點個數 <= 5000來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
方法1： 雙指針迭代法。
假設反轉對象節點為cur，反轉指向的結點為tail，反轉后tail指向的結點為首結點。具體過程如下圖：
時間復雜度： O(N)
方法2： 遞歸法。
簡單來說就是先遞進至最后一個結點，使最后一個結點為反轉鏈表的頭結點，然后在歸出的過程中是后面的結點指向前面的結點，前面的結點指向空，最終實現鏈表反轉。
時間復雜度： O(N)
編程語言：C語言
在線編程平臺：力扣
//方法1/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */struct ListNode* reverseList(struct ListNode* head){ if (head == NULL) return NULL; struct ListNode* cur = head;//反轉對象節點，初始化第1個結點 struct ListNode* next = NULL;//儲存cur下一個結點 struct ListNode* tail = NULL;//cur前插對象節點,反轉后為反轉鏈表的首結點 while (cur) { next = cur->next; cur->next = tail;//進行前插 tail = cur; cur = next; } return tail;}//方法2struct ListNode* reverseList(struct ListNode* head){ /* 特判 */ if (head == NULL || head->next == NULL) { return head; } //長度為n的鏈表，從最后一個結點開始需要進行n-1次反轉操作 //從第一個結點到最后一個結點，會進入n次reverseList()函數，除去最后一次結點只會返回最后一個結點外，其他都會進行鏈表結點反轉 //首先遞進至最后一個結點，并保存這個結點作為反轉鏈表后的頭結點 struct ListNode *next = head->next; struct ListNode *node = reverseList(next); /* 歸出過程中，每一次將結點反轉 */ next->next = head; /* 被指向的結點指向空 */ head->next = NULL; return node;}對于鏈表的反轉可以使用頭插法或者遞歸實現。當然也可以根據棧先進后出的特點，使用棧反轉鏈表。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/119008.html
摘要：導航小助手劍指從尾到頭打印鏈表題目詳情解題思路源代碼總結劍指從尾到頭打印鏈表題目詳情輸入一個鏈表的頭節點，從尾到頭反過來返回每個節點的值用數組返回。時間復雜度方法先反轉鏈表并求長度，在將反轉后的鏈表數據拷貝至數組中。 ...
摘要：問題描述輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭。通過循環遍歷當前鏈表，在遍歷過程中反轉鏈表，當前節點遍歷到最后為時，循環停止，此時當前節點為，所以它的前一個節點就是新鏈表的第一個節點。 1.問題描述 輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭。 2.思路 首先要判斷給出的頭節點是否為空，如果為空直接返回，如果不為空才可以進行反轉。因為每個節點只有一個next指針記錄它的下一個節點...
摘要：有效三角形的個數雙指針最暴力的方法應該是三重循環枚舉三個數字?？偨Y本題和三數之和很像，都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復雜度為 ...
閱讀 3098·2023-04-26 01:58
閱讀 950·2021-11-24 09:38
閱讀 3285·2021-09-03 10:29
閱讀 711·2021-08-21 14:10
閱讀 1487·2019-08-30 15:44
閱讀 3084·2019-08-30 14:10
閱讀 3210·2019-08-29 16:32
閱讀 1475·2019-08-29 12:48
