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* newHead = new ListNode(-1);
	        newHead->next = head;
	        ListNode* prev = newHead;
	        for(auto i = 0 ; i < m-1 ; i++){
	            prev = prev->next;
	        }
	        ListNode* const reversedPrev = prev;
	        //position m
	        prev = prev->next;
	        ListNode* cur = prev->next;
	        for(auto i = m ; i < n ; i++){
	            prev->next = cur->next;
	            cur->next = reversedPrev->next;
	            reversedPrev->next = cur;
	            cur = prev->next;
	        }
	        return newHead->next;
	    }
	};

ListNode* newHead = new ListNode(-1);
Can you explain this line?

It means you are defining a new node whose initial value is -1. ListNode(int x) : val(x), next(NULL) {} is the constructor.

Could you please explain your approach for the above logic? A dry run did help me understand it but how did you exactly come up with this way to rearrange the links?