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