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.
思路：
對于鏈表的問題毅戈，根據(jù)以往的經(jīng)驗(yàn)一般都是要建一個dummy node创译，連上原鏈表的頭結(jié)點(diǎn)啥酱，這樣的話就算頭結(jié)點(diǎn)變動了偎肃，我們還可以通過dummy->next來獲得新鏈表的頭結(jié)點(diǎn)施流。這道題的要求是只通過一次遍歷完成笋轨，就拿題目中的例子來說穿扳，變換的是2,3,4這三個點(diǎn)怀泊，那么我們可以先取出2躯畴，用front指針指向2民鼓，然后當(dāng)取出3的時候，我們把3加到2的前面蓬抄，把front指針前移到3丰嘉，依次類推，到4后停止嚷缭，這樣我們得到一個新鏈表4->3->2, front指針指向4饮亏。對于原鏈表連說，有兩個點(diǎn)的位置很重要阅爽，需要用指針記錄下來路幸，分別是1和5，因?yàn)楫?dāng)2,3,4被取走時付翁，原鏈表就變成了1->5->NULL简肴，要把新鏈表插入的時候需要這兩個點(diǎn)的位置。1的位置很好找百侧，因?yàn)橹續(xù)的值砰识，我們用pre指針記錄1的位置，5的位置最后才能記錄佣渴，當(dāng)4結(jié)點(diǎn)被取走后辫狼，5的位置需要記下來，這樣我們就可以把倒置后的那一小段鏈表加入到原鏈表中辛润。代碼如下：
var reverseBetween = function(head, m, n) {
var dummy=new ListNode(-1);
dummy.next=head;
var cur=dummy;
var pre,last;
for(var i=1;i<=m-1;i++){
cur=cur.next;
}
var pre=cur;
var last=cur.next;
var front=cur.next;
for(var i=m;i<=n;i++){
cur=pre.next;
pre.next=cur.next;
cur.next=front;
front=cur;
}
cur=pre.next;
pre.next=front;
last.next=cur;
return dummy.next;
};
