ReverseLinkedListII [source code]

public class ReverseLinkedListII {
static
/******************************************************************************/
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        int len = n - m + 1;
        if (len <= 1 || m < 1 || n < 1)
            return head;
        ListNode bol = new ListNode (0), slow = bol, fast = bol;
        bol.next = head;
        while (m-- > 1) if ((slow = slow.next) == null)
            return head;
        while (n-- > 0) if ((fast = fast.next) == null)
            return head;
        ListNode cur = slow.next, prev = fast.next;
        slow.next = fast;
        for (int i = 0; i < len; i++) {
            ListNode cur_next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = cur_next;
        }
        return bol.next;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ReverseLinkedListII.Solution tester = new ReverseLinkedListII.Solution();
        int[][] inputs = {
            {1,2,3,4,5}, {2,4}, {1,4,3,2,5},
            {3,5}, {1,2}, {5,3},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            ListNode head = ListNode.buildListNode (inputs[3 * i]);
            int m = inputs[3 * i + 1][0], n = inputs[3 * i + 1][1];
            System.out.println (Printer.separator ());
            String input_str = ListNode.serialize (head), output_str = ListNode.serialize (tester.reverseBetween (head, m, n)), ans_str = ListNode.serialize (ListNode.buildListNode (inputs[3 * i + 2]));
            System.out.printf ("%s and %d, %d -> %s, expected: %s\n", 
                input_str, m, n, Printer.wrap (output_str, output_str.equals (ans_str) ? 92 : 91), ans_str
            );
        }
    }
}

这个我之前做题写过, 完全不慌; 其实这里还没有搞当时写一个题目的时候最难的一个部分, 就是reverse之后的指针的advance: 因为slow和fast都换了位置, 所以下一个iteration的指针怎么更新, 并不那么trivial;

还记不记得这个reverse window当时实现的一个坑是什么? 就是循环的header, 不能判断Null, 要判断长度;

不慌不忙的AC了, 速度是4ms (16%); again, reverse LinkedList的题目, 还是注意一个草稿, 画图:

没有editorial;

https://leetcode.com/problems/reverse-linked-list-ii/discuss/30666/Simple-Java-solution-with-clear-explanation

Simply just reverse the list along the way using 4 pointers: dummy, pre, start, then

public ListNode reverseBetween(ListNode head, int m, int n) {  
    if(head == null) return null;  
    ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list  
    dummy.next = head;  
    ListNode pre = dummy; // make a pointer pre as a marker for the node before reversing  
    for(int i = 0; i<m-1; i++) pre = pre.next;  

    ListNode start = pre.next; // a pointer to the beginning of a sub-list that will be reversed  
    ListNode then = start.next; // a pointer to a node that will be reversed  

    // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3  
    // dummy-> 1 -> 2 -> 3 -> 4 -> 5  

    for(int i=0; i<n-m; i++)  
    {  
        start.next = then.next;  
        then.next = pre.next;  
        pre.next = then;  
        then = start.next;  
    }  

    // first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4  
    // second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)  

    return dummy.next;  
}

大概理解了一下, 这个思路还是很清晰的; 这个就是一个完全ad-hoc的思路了, 而不是对第一题的一个拓展; 对比我的算法, 他的算法的优势在于, 比我少N-M个access;

然后他的这个操作的原理其实也是挺有意思的:

可以看到, 如果你理解了, 你就发现他这里这个操作实际上很像是一个queue操作(右边是head位置), 每一个iteration他实际上就是从右边不断的挤出来一个, 然后push到end, 也就是pre.next的位置;

反过来想, 如果以后有人跟你说, 用LinkedList来实现一个queue, 你会吗? 类似这里的思想, 实际上比较重要的就是三个指针, pre head, 然后最后的两个位置的指针;

不对啊, 这个哪里是queue啊;

可以看到, 实际上是比如你有1 2 3 4, 从2开始, 然后3, 然后4, 每一次提取出来一个, 丢到最左边; 所以这个reverse实际上是一个通过最基本的delete和insert的操作完成的;

https://leetcode.com/problems/reverse-linked-list-ii/discuss/30744/Share-my-14-lines-C++-solution

ListNode *reverseBetween(ListNode *head, int m, int n) {  
    if(m==n)return head;  
    n-=m;  
    ListNode prehead(0);  
    prehead.next=head;  
    ListNode* pre=&prehead;  
    while(--m)pre=pre->next;          
    ListNode* pstart=pre->next;  
    while(n--)  
    {  
        ListNode *p=pstart->next;  
        pstart->next=p->next;  
        p->next=pre->next;  
        pre->next=p;  
    }  
    return prehead.next;  
}

好像跟上面差不多的思路;

https://leetcode.com/problems/reverse-linked-list-ii/discuss/30668/12-lines-4ms-C++

The basic idea is as follows:

1. Create a new_head that points to head and use it to locate the immediate node before the m-th (notice that it is 1-indexed) node pre;
2. Set cur to be the immediate node after pre and at each time move the immediate node after cur (named move) to be the immediate node after pre. Repeat it for n - m times.

class Solution {    
public:  
    ListNode* reverseBetween(ListNode* head, int m, int n) {  
        ListNode* new_head = new ListNode(0);  
        new_head -> next = head;  
        ListNode* pre = new_head;  
        for (int i = 0; i < m - 1; i++)  
            pre = pre -> next;  
        ListNode* cur = pre -> next;  
        for (int i = 0; i < n - m; i++) {  
            ListNode* move = cur -> next;   
            cur -> next = move -> next;  
            move -> next = pre -> next;  
            pre -> next = move;  
        }  
        return new_head -> next;  
    }  
};

好像跟之前那个queue一样的做法是差不多的;

Your solution yields a memory leak, since the dummy head is created on the heap and not deleted later on. Apart from that, it is generally better to create the dummy head on the stack to avoid unnecessary heap fragmentation. (It is also not necessary to introduce it here at all, but this is already a matter of taste)

submission最优解, 不过其实也是波动:

class Solution {  
    public ListNode reverseBetween(ListNode head, int m, int n) {  
        if(head == null || head.next == null){  
            return head;  
        }  

        ListNode dummy = new ListNode(0);  
        dummy.next = head;  
        ListNode prev = dummy;  

        for(int i = 0; i < m - 1; i++){  
            prev = prev.next;  
        }  

        ListNode start = prev.next;  
        ListNode then = start.next;  

        for(int j = m; j < n; j++){  

            start.next = then.next;  
            then.next = prev.next;  
            prev.next = then;  
            then = start.next;  
        }  

        return dummy.next;  
    }  
}

Problem Description

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.

Difficulty:Medium
Total Accepted:131.7K
Total Submissions:421.8K
Contributor:LeetCode
Related Topics
linked list
Similar Questions
Reverse Linked List