Reverse Linked List II （链表的前插操作）

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.

 这一题的主要就是链表的逆序，逆序比较好的解法有前插，利用栈，这里我们使用前插的方式解决

先看代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head==null||m==n)
            return head;
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode mPre=dummy;
        ListNode mNode=head;
        int i=1;
        while(i<m){
            mPre=mPre.next;
            mNode=mNode.next;
            i++;
        }
        while(i<n){//前插
            ListNode temp=mPre.next;
            mPre.next=mNode.next;
            mNode.next=mNode.next.next;
            mPre.next.next=temp;
            i++;
        }
        return dummy.next;
    }
}

 首先需要找到m节点和m节点的前节点。

找到m节点和其前节点后我们就可以进行前插了。

ListNode temp=mPre.next;//现将mPre的后面一个节点保存起来。插入的时候就是讲其他节点插入mPre和mPre后面一个节点之间，所以要保存mPre的后一个节点

 

mPre.next=mNode.next;//mNode.next指向要插入的节点。将此节点作为mPre的next节点

 

mNode.next=mNode.next.next;//mNode的next指针指向他的下下个节点

 

mPre.next.next=temp;//将插入节点的next指针指向我们之前保存的节点。完成节点的插入