leetcode92. Reverse Linked List II

luzhuqun 發(fā)布于2019-08-15 10:51 / 2534人閱讀

摘要：題目要求將鏈表中從第個(gè)節(jié)點(diǎn)開始翻轉(zhuǎn)至第個(gè)節(jié)點(diǎn)結(jié)束。要求在第一次遍歷中即完成該過(guò)程。將從第一個(gè)該節(jié)點(diǎn)開始依次插入最后一個(gè)節(jié)點(diǎn)后面直到遇到最后一個(gè)節(jié)點(diǎn)。最后我們還需要一個(gè)節(jié)點(diǎn)來(lái)標(biāo)記整個(gè)鏈表的起始節(jié)點(diǎn)。

題目要求

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ? m ? n ? length of list.

將鏈表中從第m個(gè)節(jié)點(diǎn)開始翻轉(zhuǎn)至第n個(gè)節(jié)點(diǎn)結(jié)束。要求在第一次遍歷中即完成該過(guò)程。

思路一：管他的一次遍歷

直觀點(diǎn)想，我們只需要知道開始翻轉(zhuǎn)的第一個(gè)節(jié)點(diǎn)和需要翻轉(zhuǎn)的最后一個(gè)節(jié)點(diǎn)。將從第一個(gè)該節(jié)點(diǎn)開始依次插入最后一個(gè)節(jié)點(diǎn)后面直到遇到最后一個(gè)節(jié)點(diǎn)。該算法的時(shí)間復(fù)雜度為O(2n-m),即O(n+n-m)

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(m==n) return head;
        ListNode dummy1 = new ListNode(0), dummy2 = new ListNode(0), start = new ListNode(0);
        dummy1.next = head;
        dummy2.next = head;
        start.next = dummy2;
        for(int i = 0 ; i 
思路二：one pass
那么有沒(méi)有辦法正向翻轉(zhuǎn)呢。當(dāng)然是可以的啦，換句話說(shuō)，我們只要將節(jié)點(diǎn)不斷往前插入就行啦。舉題中的例子。1->2->3->4->5->NULL, m = 2 n = 4,
首先我們將數(shù)值3提取出來(lái)插入到1和2之間1-3-2-4-5
之后將數(shù)值4提取出來(lái)插入到1和2之間1-4-3-2-5
至此翻轉(zhuǎn)結(jié)束。
也就是說(shuō)我們?cè)谶@個(gè)過(guò)程中需要知道3個(gè)節(jié)點(diǎn)，開始翻轉(zhuǎn)的前一個(gè)節(jié)點(diǎn)prev，開始翻轉(zhuǎn)的節(jié)點(diǎn)start，以及插入到前面的這個(gè)節(jié)點(diǎn)then。
最后我們還需要一個(gè)dummy節(jié)點(diǎn)來(lái)標(biāo)記整個(gè)鏈表的起始節(jié)點(diǎn)。
代碼如下：
    public ListNode reverseBetween2(ListNode head, int m, int n){
        if(m==n || head==null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        for(int i = 0 ; i

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~