五十路视频在线,日韩免费黄色电影,免费无人区一区二区三区,国产一级毛片电影,亚洲婷婷在线,ThePorn精品无码,网红鹿少女演绎点外卖视频,午夜三级无码在线看

Python實戰(zhàn)社群

Java實戰(zhàn)社群

長按識別下方二維碼，按需求添加

掃碼關(guān)注添加客服

進(jìn)Python社群▲

掃碼關(guān)注添加客服

進(jìn)Java社群▲

作者丨編程狂想曲

來源丨編程狂想曲

今天分享的內(nèi)容就是關(guān)于如何用遞歸思想來反轉(zhuǎn)鏈表的，分享的題目是：

LeetCode?#206?反轉(zhuǎn)鏈表
LeetCode?#92 反轉(zhuǎn)鏈表||

友情提示：在用遞歸思想解題時，明確遞推公式的含義后，不要試圖想明白每一步是如何遞歸的，這很容易把自己繞暈哈。

LeetCode #206 反轉(zhuǎn)鏈表

題目描述：

反轉(zhuǎn)一個單鏈表。

示例:

輸入: 1->2->3->4->5->NULL

輸出: 5->4->3->2->1->NULL

思路分析：

示例給出的鏈表，如下圖所示：

遞歸解題首先要做的是明確遞推公式的含義，在這里對于head指向結(jié)點1來說，它只需要知道它之后的所有節(jié)點反轉(zhuǎn)之后的結(jié)果就可以了，也就是說遞推公式reverseList的含義是：把拿到的鏈表進(jìn)行反轉(zhuǎn)，然后返回新的頭結(jié)點。

結(jié)點1之后的結(jié)點，經(jīng)過遞歸公式reverseList處理之后的結(jié)果如下圖：

到這里，就可以寫出如下的代碼了。

public ListNode reverseList(ListNode head) {    // 調(diào)用遞推公式反轉(zhuǎn)當(dāng)前結(jié)點之后的所有節(jié)點    // 返回的結(jié)果是反轉(zhuǎn)后的鏈表的頭結(jié)點    ListNode newHead = reverseList(head.next);}

接著要做的就是反轉(zhuǎn)head指向的結(jié)點1，也就是將head指向的結(jié)點作為其下一個結(jié)點的下一個結(jié)點，即head.next.next=head。

最后，將head指向的結(jié)點的下一個結(jié)點置為null，就完成了整個鏈表的反轉(zhuǎn)。

將反轉(zhuǎn)head指向的結(jié)點的代碼完善之后，就可以得到如下的代碼：

public ListNode reverseList(ListNode head) {    // 調(diào)用遞推公式反轉(zhuǎn)當(dāng)前結(jié)點之后的所有節(jié)點    // 返回的結(jié)果是反轉(zhuǎn)后的鏈表的頭結(jié)點    ListNode newHead = reverseList(head.next);    head.next.next = head;    head.next = null;    return newHead;}

遞歸調(diào)用這一部分完成之后，還有重要的一步就是遞歸終止條件，遞歸反轉(zhuǎn)鏈表什么時候停止呢？在head指向的結(jié)點為null或head指向的結(jié)點的下一個結(jié)點為null時停止，因為在這兩種情況下，反轉(zhuǎn)后的結(jié)果就是它自己。到這里，就可以寫出完整的代碼了：

public ListNode reverseList(ListNode head) {    if (head == null || head.next == null) {        return head;    }
    // 調(diào)用遞推公式反轉(zhuǎn)當(dāng)前結(jié)點之后的所有節(jié)點    // 返回的結(jié)果是反轉(zhuǎn)后的鏈表的頭結(jié)點    ListNode newHead = reverseList(head.next);    head.next.next = head;    head.next = null;    return newHead;}

LeetCode #92?反轉(zhuǎn)鏈表||

題目描述：

反轉(zhuǎn)從位置 m 到 n 的鏈表。請使用一趟掃描完成反轉(zhuǎn)。

說明:
1 ≤ m ≤ n ≤ 鏈表長度。

示例:

輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL

思路分析：

為了方便說明一個問題，這里以鏈表1->2->3->4->5->6->NULL, m = 3, n = 5為例進(jìn)行分析如何用遞歸思想求解該題目。

在這里head指向的結(jié)點1，不用關(guān)注其后的所有結(jié)點時如何將m=3與n=5之間的部分反轉(zhuǎn)的，它只需要知道反轉(zhuǎn)后的結(jié)果就可以。也就是說，在這里遞推公式reverseBetween的含義是：將拿到的鏈表反轉(zhuǎn)，然后返回反轉(zhuǎn)后的鏈表的頭結(jié)點。

這樣就可以初步寫出如下的代碼：

public ListNode reverseBetween(ListNode head, int m, int n) {    ListNode between = reverseBetween(head.next, m-1,n-1);}

接著要做的就是，將遞推公式reverseBetween返回的結(jié)果，掛在head之后，即head.next=between。

這時，代碼可以進(jìn)一步完善，如下所示：

public ListNode reverseBetween(ListNode head, int m, int n) {    ListNode between = reverseBetween(head.next, m-1,n-1);    head.next = between;    return head;}

遞推公式的部分已經(jīng)完成了，接著要明確的就是遞歸終止條件。在這里原問題是反轉(zhuǎn)鏈表：1->2->3->4->5->6->NULL, m = 3, n = 5之間的部分。

更小的子問題是反轉(zhuǎn)鏈表：2->3->4->5->6->NULL, m = 2, n = 4之間的部分。

在進(jìn)一步是反轉(zhuǎn)鏈表：3->4->5->6->NULL, m = 1, n = 3之間的部分。但是，這時這個子問題和上一個子問題還是可以用相同思路求解的同一個子問題嗎？

不是。

原因在于對于子問題：2->3->4->5->6->NULL, m = 2, n = 4來說，它只需要將其之后的所有結(jié)點反轉(zhuǎn)之后的結(jié)點掛在自己之后就可以了。但是，對于問題3->4->5->6->NULL, m = 1, n = 3來說，結(jié)點3本身也是需要反轉(zhuǎn)的。

對于如何用遞歸思想反轉(zhuǎn)3->4->5->6->NULL, m = 1, n = 3一會兒再說。到這里，遞歸終止條件就明了了，即m=1時停止，代碼如下：

public ListNode reverseBetween(ListNode head, int m, int n) {    if (m == 1) {        return 待補(bǔ)充;    }
    ListNode between = reverseBetween(head.next, m-1,n-1);    head.next = between;    return head;}

說明：以下部分是借鑒的labuladong大佬新作《labuladong的算法小抄》一書中的相關(guān)內(nèi)容。

接著我們看下如何用遞歸思想反轉(zhuǎn)3->4->5->6->NULL, m = 1, n = 3，即如何反轉(zhuǎn)鏈表的前n個結(jié)點。

這里，遞推公式reverseTopN的含義是反轉(zhuǎn)鏈表的前n個結(jié)點并返回被反轉(zhuǎn)的鏈表的頭結(jié)點。因此，其需要的參數(shù)有兩個，一是待反轉(zhuǎn)的鏈表的頭結(jié)點，二是反轉(zhuǎn)前幾個結(jié)點，即n。

對于鏈表4->5->6->NULL, n = 2來說，經(jīng)過遞推公式reverseTopN處理之后，結(jié)果如下圖所示：

至此，對于反轉(zhuǎn)鏈表的前n個結(jié)點，可以初步寫出如下的代碼：

private ListNode reverseTopN(ListNode head, int n) {    ListNode newHead = reverseTopN(head.next, n-1);}

經(jīng)過前面分析，我們知道head指向的結(jié)點3也是需要反轉(zhuǎn)的，即head.next.next=head。但是，我們發(fā)現(xiàn)在完成這一步操作后，結(jié)點6沒法在和其它結(jié)點產(chǎn)生聯(lián)系了。

這個問題怎么解決呢？我們可以用topNSuccessor這個變量，指向第n個結(jié)點之后的結(jié)點。

這時，在反轉(zhuǎn)結(jié)點3，即head.next.next=head之后，我們可以將topNSuccessor指向的結(jié)點掛在head指向的結(jié)點之后，即head.next=topNSuccessor。

head.next.next=head

head.next=topNSuccessor

這時，反轉(zhuǎn)鏈表前N個結(jié)點的代碼進(jìn)一步完善如下：

private ListNode reverseTopN(ListNode head, int n) {    ListNode newHead = reverseTopN(head.next, n-1);    head.next.next = head;    head.next = topNSuccessor;    return newHead;}

這時就有一個問題，topNSuccessor怎么確定的呢？

我們先看下反轉(zhuǎn)鏈表前n個結(jié)點的遞歸終止條件是什么。當(dāng)只需要反轉(zhuǎn)鏈表的第一個結(jié)點時，返回原鏈表就可以了，即反轉(zhuǎn)鏈表前n個結(jié)點的遞歸終止條件是n==1。

如下圖，當(dāng)n==1時，我們就可以確定topNSuccessor是head指向的結(jié)點的下一個結(jié)點。

到這里反轉(zhuǎn)鏈表的前n個結(jié)點的代碼就可以完善了，具體代碼如下：

ListNode topNSuccessor = null;
private ListNode reverseTopN(ListNode head, int n) {    if (n == 1) {        topNSuccessor = head.next;        return head;    }
    ListNode newHead = reverseTopN(head.next, n-1);    head.next.next = head;    head.next = topNSuccessor;    return newHead;}

最后，反轉(zhuǎn)從位置 m 到 n 的鏈表的遞歸實現(xiàn)完整代碼如下：

public ListNode reverseBetween(ListNode head, int m, int n) {    if (m == 1) {        return reverseTopN(head, n);    }
    ListNode between = reverseBetween(head.next, m-1,n-1);    head.next = between;    return head;}
ListNode topNSuccessor = null;
private ListNode reverseTopN(ListNode head, int n) {    if (n == 1) {        topNSuccessor = head.next;        return head;    }
    ListNode newHead = reverseTopN(head.next, n-1);    head.next.next = head;    head.next = topNSuccessor;    return newHead;}

參考資料：《labuladong的算法小抄》

題圖：rahu / Pixabay

程序員專欄
?掃碼關(guān)注填加客服?
長按識別下方二維碼進(jìn)群

近期精彩內(nèi)容推薦：??

?幾句話，離職了

?中國男性的私密數(shù)據(jù)大賞，女生勿入！

?為什么很多人用“ji32k7au4a83”作密碼？

?一個月薪 12000 的北京程序員的真實生活！

在看點這里好文分享給更多人↓↓

遞歸反轉(zhuǎn)鏈表，怎么就不會了呢

遞歸反轉(zhuǎn)鏈表，怎么就不會了呢