反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
把从m到n的反转，
然后再接上去。
class Solution
{
public:
ListNode * reverseBetween(ListNode* head, int m, int n)
{
int cnt = 0;
ListNode* ansHead = NULL;
ListNode* reverseHead = NULL;
ListNode* lastNode = NULL;
ListNode* tail = NULL;
while (head != NULL)
{
ListNode *node = new ListNode(head->val);
cnt++;
if (cnt == m && m != n)
{
tail = lastNode;
if (reverseHead == NULL)
{
reverseHead = node;
lastNode = reverseHead;
head = head->next;
}
while (head != NULL)
{
ListNode *node = new ListNode(head->val);
cnt++;
node->next = lastNode;
lastNode = node;
head = head->next;
if (cnt == n)
{
break;
}
}
if (tail == NULL)
{
ansHead = lastNode;
lastNode = reverseHead;
}
else
{
tail->next = lastNode;
lastNode = reverseHead;
}
}
else
{
if (ansHead == NULL)
{
ansHead = node;
lastNode = ansHead;
}
else
{
lastNode->next = node;
lastNode = node;
}
head = head->next;
}
}
return ansHead;
}
};