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