学步园

题目

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 个进行逆向

思路

1  首先看到1 ≤ m ≤ n ≤
length of list，很开心，一些特殊数字不用处理了。之后思考逆向链接链表的方式。如果可以有栈的帮忙，可以把需要的入栈，然后依次出栈即可。题目要求in-place，继续思考。可以用三个指针precur ,cur ,head，cur 来运算是否到null，precur来表示要处理的，指向上一次的头，也就是head，然后更新自己为新的头。这里因为在当中，所以还需要一些辅助的指针来帮忙实现。

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head== null|| m==n){
            return head;
        }
        ListNode dummynode = new ListNode(Integer.MIN_VALUE);
        dummynode.next = head;
        ListNode outstart = dummynode;
       
        int i;
        for( i=1;i<m;i++){
            outstart=outstart.next;
        }
        ListNode inend = outstart.next;
        ListNode instart = null;
        ListNode cur = outstart.next;
        ListNode outend = null;
        while(i<=n){
            ListNode precur = cur;
            cur=cur.next;
            if(i==n){
                outend=precur.next;
            }
            precur.next=instart;
            instart=precur;
            i++;
        }
        outstart.next = instart;
        if(inend!=null){
            inend.next=outend;
        }
        return dummynode.next;
    }
}