[LeetCode]Reverse Linked List II

找到reverse的起始节点，之后就和Reverse Linked List是一样的题目了。我们用循环来做，注意这里reverse之后head是可能会变的，所以我们在head节点之前加一个helper节点，最后return的时候return helper->next即可。O(N)时间，常数空间。代码如下：

	/**
	* 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* helper = new ListNode(-1);
	helper->next = head;
	ListNode* curr = helper;
	for(int i = 0; i < m - 1; ++i)
	curr = curr->next;
	curr->next = reverse(curr->next, n - m);
	return helper->next;
	}
	private:
	ListNode* reverse(ListNode* head, int k)
	{
	ListNode* curr = head->next, *prev = head;
	while(curr && k--)
	{
	ListNode* tmp = curr->next;
	curr->next = prev;
	prev = curr;
	curr = tmp;
	}
	head->next = curr;
	return prev;
	}
	};

view raw Reverse Linked List II.cpp hosted with ❤ by GitHub