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

reverseListBetweenMandN.md

##Leetcode-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.

Analysis

  --------->1------>2------->3------->4-------5------->nullptr
  ^         ^       ^       ^         ^       ^
  |         |       |       |         |       |
  |         |       |       |         |       |
  |         |       |       |         |       |
HeadPrev  head  constPrev  prev      cur  cur->next

假设目前的m是3,n是5，那么prev-next指向cur->next,cur指向
constPrev->next,constPrev->next指向cur，然后更新cur至prev->next
思想是头插法交换node

  --------->1------>2------->4------->3-------5------->nullptr
  ^         ^       ^       ^         ^       ^
  |         |       |       |         |       |
  |         |       |       |         |       |
  |         |       |       |         |       |
HeadPrev  head  constPrev        	prev  	 cur
最后返回HeadPrev的next节点即可

Code

	/**
	 * Definition for singly-linked list.
	 * struct ListNode {
	 *     int val;
	 *     ListNode *next;
	 *     ListNode(int x) : val(x), next(NULL) {}
	 * };
	 */
	class Solution {
	public:
	    ListNode *reverseBetween(ListNode *head, int m, int n) {
	    	ListNode *prev = head; 
		for(auto i = 0 ; i < start-1 ; i++){
		    prev = prev->next;
		}
	        ListNode* const reversedPrev = prev;
        	//position m
        	prev = prev->next;
        	Node* cur = prev->next;
		for(auto i = start ; i < end ; i++){
		    prev->next         = cur->next;
		    cur->next          = reversedPrev->next;
		    reversedPrev->next = cur;
		    cur                = prev->next;
		}
		return head;
	    };