[LeetCode] Reverse Linked List II

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.

思路：

反转整个链表的变种，指定了起点和终点。由于m=1时会变动头节点，所以加入一个dummy头节点

1. 找到原链表中第m-1个节点start：反转后的部分将接回改节点后。

从dummy开始移动m-1步

D->1->2->3->4->5->NULL

       |

      st

2. 将从p = start->next开始，长度为L = n-m+1的部分链表反转。

            __________

            |                  |

            |                 V

D->1->2<-3<-4    5->NULL             

       |     |           | 

      st    p          h0         

3. 最后接回

            __________

            |                  |

            |                 V

D->1   2<-3<-4    5->NULL             

       |________|                

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public: ListNode *reverseBetween(ListNode *head, int m, int n) { if(m<1 || m>=n || !head) return head; ListNode *dummy = new ListNode(0); dummy->next = head; head = dummy; // move head to (m-1)th node for(int i=0; i<m-1; i++) head = head->next; // reverse list from pre with length n-m+1 ListNode *pre = head->next, *cur = pre->next; for(int i=0; i<n-m; i++) { ListNode *temp = cur->next; cur->next = pre; pre = cur; cur = temp; } head->next->next = cur; head->next = pre; head = dummy->next; delete dummy; return head; } };