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