資訊專欄INFORMATION COLUMN
摘要：示例輸入輸出進(jìn)階你可以迭代或遞歸地反轉(zhuǎn)鏈表?？梢栽O(shè)置一個(gè)指針，指向，保證后續(xù)的操作然后將，往前挪動(dòng)，當(dāng)然還有，直到為空，這時(shí)指向反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)。接下來考慮遞歸結(jié)束的條件非常顯然，子鏈表只有一個(gè)節(jié)點(diǎn)是遞歸結(jié)束，直接返回該節(jié)點(diǎn)。
本文來自 SoulOH 的CSDN 博客 ，原文地址請(qǐng)點(diǎn)擊：https://blog.csdn.net/SoulOH/...
題目:
反轉(zhuǎn)一個(gè)單鏈表。
示例:
輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL
進(jìn)階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題？
解答：
迭代方式：首先判斷鏈表是不是空的，如果是空的，直接返回null；
對(duì)于鏈表：
放兩個(gè)指針p1, p2:
不能直接將p2 -> next指向p1，否則鏈表會(huì)斷掉。
可以設(shè)置一個(gè)tmp指針，指向 p2 -> next，保證后續(xù)的操作：
然后將p1，p2往前挪動(dòng)，當(dāng)然還有tmp，直到p2為空，這時(shí)p1指向反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)。
最后一次：
剛好結(jié)束的時(shí)候：
完成了？
不。好像有一點(diǎn)不對(duì)勁兒，還多了一個(gè)1 -> 2的指針，少了一個(gè)null（1 -> null）。正巧head還在，通過head -> next訪問多余的指針，指向null（其實(shí)一開始就可以這么干的。）
實(shí)現(xiàn)代碼：
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
//迭代
if (head == null || head.next == null) return head;
var p1 = head;
var p2 = head.next;
p1.next = null;
while (p2 !== null) {
var temp = p2.next;
p2.next = p1;
p1 = p2;
p2 = temp;
}
return p1;
};
遞歸方式：
我們可以從另一個(gè)角度考慮這件事：
同樣地，對(duì)于這樣一個(gè)鏈表：
我們要反轉(zhuǎn)它，其實(shí)可以
然后我們當(dāng)作這個(gè)子鏈表已經(jīng)反轉(zhuǎn)完成：
而我們需要的是：
于是我們可以將上上張圖的head.next.next = head：像是這樣：
然而僅僅這樣是不夠的，鏈表到現(xiàn)在有一個(gè)明顯的環(huán)，我們要把這個(gè)環(huán)去掉：
令head.next = null即可。
完成。
接下來考慮遞歸結(jié)束的條件：非常顯然，子鏈表只有一個(gè)節(jié)點(diǎn)是遞歸結(jié)束，直接返回該節(jié)點(diǎn)。
當(dāng)然，這個(gè)可以和一開始的空值處理（空鏈表的處理）寫到一起。
下面是具體實(shí)現(xiàn)：
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
//遞歸
if (head == null || head.next == null) return head;
var res = reverseList(head.next);
head.next.next = head;
head.next = null;
return res;
};
本文來自 SoulOH 的CSDN 博客 ，原文地址請(qǐng)點(diǎn)擊：https://blog.csdn.net/SoulOH/...
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/97989.html
摘要：算法思路兩種方法一般反轉(zhuǎn)遞歸法一般解決定義三個(gè)指針，分別為，存儲(chǔ)當(dāng)前結(jié)點(diǎn)，指向反轉(zhuǎn)好的結(jié)點(diǎn)的頭結(jié)點(diǎn)，存儲(chǔ)下一結(jié)點(diǎn)信息。遞歸法重點(diǎn)分析先確定終止條件當(dāng)下一結(jié)點(diǎn)為時(shí)，返回當(dāng)前節(jié)點(diǎn)判斷當(dāng)前的鏈表是否為遞歸找到尾結(jié)點(diǎn)，將其存儲(chǔ)為頭結(jié)點(diǎn)。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿 題目：Reverse...
摘要：反轉(zhuǎn)一個(gè)單鏈表。示例輸入輸出進(jìn)階你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題解題思路每次遍歷到最后一位取節(jié)點(diǎn)這種方法就算了時(shí)間復(fù)雜度太高。從鏈表末尾向頭部逐個(gè)分離節(jié)點(diǎn)，并將節(jié)點(diǎn)添加到新鏈表的末尾。與迭代法原理相似。 反轉(zhuǎn)一個(gè)單鏈表。 Reverse a singly linked list. 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2...
摘要：反轉(zhuǎn)一個(gè)單鏈表。示例輸入輸出進(jìn)階你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題解題思路每次遍歷到最后一位取節(jié)點(diǎn)這種方法就算了時(shí)間復(fù)雜度太高。從鏈表末尾向頭部逐個(gè)分離節(jié)點(diǎn)，并將節(jié)點(diǎn)添加到新鏈表的末尾。與迭代法原理相似。 反轉(zhuǎn)一個(gè)單鏈表。 Reverse a singly linked list. 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2...
摘要：給定一個(gè)鏈表，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng)個(gè)位置，其中是非負(fù)數(shù)。按上述思路解，與旋轉(zhuǎn)數(shù)組那道題大同小異，來介紹另一種很簡(jiǎn)單高效的方法。只需在第個(gè)節(jié)點(diǎn)之后切斷，首尾連接即可。另外可能大于鏈表長(zhǎng)度，應(yīng)當(dāng)做求余運(yùn)算。 ?給定一個(gè)鏈表，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(shù)。 Given a linked list, rotate the list to the ...
閱讀 3268·2023-04-25 22:47
閱讀 3778·2021-10-11 10:59
閱讀 2313·2021-09-07 10:12
閱讀 4269·2021-08-11 11:15
閱讀 3440·2019-08-30 13:15
閱讀 1757·2019-08-30 13:00
閱讀 976·2019-08-29 14:02
閱讀 1691·2019-08-26 13:57
