reverse linked list II

reverse linked list II

not hard

add a head before head, and walk m step and then reverse n-m+1 element. After that connect the reset list.Watch out! m<=n .

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *reverseBetween(ListNode *head, int m, int n) {
12         if ( !head || n == m ) {
13             return head;
14         }
15         ListNode* h = new ListNode(-1);
16         h->next = head;
17         ListNode* p = h;
18         int t = 1;
19         while ( t < m ) {
20             t++;
21             p = p->next;
22         }
23         ListNode* q = p->next;
24         p->next = NULL;
25         ListNode* qnext = NULL;
26         ListNode* r = NULL;
27         while ( t <= n ) {
28             qnext = q->next;
29             q->next = p->next;
30             if ( NULL == r ) {
31                 r = q;
32             }
33             p->next = q;
34             q = qnext;
35             t++;
36         }
37         r->next = q;
38         head = h->next;
39         delete(h);
40         return head;
41     }
42 };

Loading Disqus comments...
Table of Contents