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 = 4 Output: 1->4->3->2->5->NULL
根据经验,先建立一个虚结点dummy node,连上原链表的头结点,这样的话就算头结点变动了,我们还可以通过dummy->next来获得新链表的头结点。
步骤一:找到要倒置的链表起始位置的前一个,记为pre。
步骤二:从m-n倒置,移位m-n次,每一次cur的位置不变,利用临时结点t记录cur的下一个位置t=cur->next,t是即将倒置的下一个结点,故将cur的next指向t的下一个结点cur->next=t->next,t结点放置在发生倒置的起始位置,也就是t的next指向pre的next,t->next=pre->next,将pre的next指向t。
步骤三:返回虚结点的next。
方法一:(C++)
1 class Solution { 2 public: 3 ListNode* reverseBetween(ListNode* head, int m, int n) { 4 ListNode* dummy=new ListNode(-1),* pre=dummy; 5 pre->next=head; 6 int index=0; 7 while(pre){ 8 if(index==m-1) 9 break; 10 index++; 11 pre=pre->next; 12 } 13 ListNode* cur=pre->next; 14 for(int index=m;index<n;index++){ 15 ListNode* t=cur->next; 16 cur->next=t->next; 17 t->next=pre->next; 18 pre->next=t; 19 } 20 return dummy->next; 21 } 22 };