Reverse a linked list from position?m?to?n. Do it in one-pass.
Note:?1 ≤?m?≤?n?≤ length of list.
Example:
Input:1->2->3->4->5->NULL,m= 2,n= 4Output:1->4->3->2->5->NULL
本題要求在一個(gè)鏈表中，顛倒第m個(gè)-第n個(gè)節(jié)點(diǎn)拇泛，形成新的鏈表（從第一個(gè)節(jié)點(diǎn)算起，不是第0個(gè)）刻恭。
首先建立dummy節(jié)點(diǎn)指向頭結(jié)點(diǎn)实檀，接著找前置節(jié)點(diǎn)缸沃，即第m-1個(gè)節(jié)點(diǎn)宜咒。算法的思想是依次將第m+1飒责、第m+2赘娄、...、第n個(gè)節(jié)點(diǎn)放到pre節(jié)點(diǎn)后宏蛉。設(shè)cur節(jié)點(diǎn)為第m個(gè)節(jié)點(diǎn)遣臼。則在每次變換位置的循環(huán)中，首先找到cur節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)t拾并，cur的next指向t的next揍堰，t的next指向pre的next蚌讼，pre的next指向t。
ListNode *reverseBetween(ListNode *head, int m, int n) {
? ? ? ? ListNode *dummy = new ListNode(-1), *pre = dummy;
? ? ? ? dummy->next = head;
? ? ? ? for (int i = 0; i < m - 1; ++i) pre = pre->next;
? ? ? ? ListNode *cur = pre->next;
? ? ? ? for (int i = m; i < n; ++i) {
? ? ? ? ? ? ListNode *t = cur->next;
? ? ? ? ? ? cur->next = t->next;
? ? ? ? ? ? t->next = pre->next;
? ? ? ? ? ? pre->next = t;
? ? ? ? }
? ? ? ? return dummy->next;
? ? }
