19.2.24 [LeetCode 92] Reverse Linked List II

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

 1 class Solution {
 2 public:
 3     ListNode* reverseBetween(ListNode* head, int m, int n) {
 4         ListNode*mnode = head, *nnode = head, *bef = NULL, *aft = NULL, *now = head;
 5         int cnt = 1;
 6         while (now) {
 7             if (cnt == m - 1)
 8                 bef = now;
 9             else if (cnt == m)
10                 mnode = now;
11             if (cnt == n) {
12                 nnode = now;
13                 aft = nnode->next;
14                 break;
15             }
16             now = now->next;
17             cnt++;
18         }
19         nnode->next = NULL;
20         if(bef)
21             bef->next = NULL;
22         while (mnode) {
23             ListNode*next = mnode->next;
24             mnode->next = aft;
25             aft = mnode, mnode = next;
26         }
27         if (bef) {
28             bef->next = nnode;
29             return head;
30         }
31         return nnode;
32     }
33 };

View Code