leetcode92. Reverse Linked List II

luzhuqun 發布于2019-08-15 10:51 / 2529人閱讀

摘要：題目要求將鏈表中從第個節點開始翻轉至第個節點結束。要求在第一次遍歷中即完成該過程。將從第一個該節點開始依次插入最后一個節點后面直到遇到最后一個節點。最后我們還需要一個節點來標記整個鏈表的起始節點。

題目要求

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個節點開始翻轉至第n個節點結束。要求在第一次遍歷中即完成該過程。

思路一：管他的一次遍歷

直觀點想，我們只需要知道開始翻轉的第一個節點和需要翻轉的最后一個節點。將從第一個該節點開始依次插入最后一個節點后面直到遇到最后一個節點。該算法的時間復雜度為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
那么有沒有辦法正向翻轉呢。當然是可以的啦，換句話說，我們只要將節點不斷往前插入就行啦。舉題中的例子。1->2->3->4->5->NULL, m = 2 n = 4,
首先我們將數值3提取出來插入到1和2之間1-3-2-4-5
之后將數值4提取出來插入到1和2之間1-4-3-2-5
至此翻轉結束。
也就是說我們在這個過程中需要知道3個節點，開始翻轉的前一個節點prev，開始翻轉的節點start，以及插入到前面的這個節點then。
最后我們還需要一個dummy節點來標記整個鏈表的起始節點。
代碼如下：
    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

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 linked Reverse Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67385.html

[LeetCode] Reverse Linked List I & II

Reverse Linked List Reverse a singly linked list. Note Create tail = null; Head loop through the list: Store head.next, head points to tail, tail becomes head, head goes to stored head.next; Return t...

jcc 2019-08-14 14:55 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
[Leetcode] Reverse Linked List 反轉鏈表

摘要：先跳過前個節點，然后初始化好這五個指針后，用中的方法反轉鏈表。完成了第個節點的反轉后，將子鏈反轉前的頭節點的設為子鏈反轉過程中的下一個節點，將子鏈反轉前頭節點前面一個節點的設為子鏈反轉過程中的當前節點。 Reverse Linked List I Reverse a singly linked list. click to show more hints. Hint: A linke...

Eminjannn 2019-08-14 12:28 評論0 收藏0