2013.12.31 16:00

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.

Solution1:

　　Reversing a linked list is typical for a technical interview, but this variation is a bit more diffcult.

　　My solution, is to cut the list into three parts: [1, m - 1], [m, n], [n + 1, end], locate the middle part, reverse it and restore the pointers at last.

　　Time complexity is O(n), space compexity is O(1).

Accepted code:

1 // 3RE, 1WA, 1AC, so difficult... 2 /** 3  * Definition for singly-linked list. 4  * struct ListNode { 5  *     int val; 6  *     ListNode *next; 7  *     ListNode(int x) : val(x), next(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     ListNode *reverseBetween(ListNode *head, int m, int n) {13         // IMPORTANT: Please reset any member data you declared, as14         // the same Solution instance will be reused for each test case.15         int i;16         ListNode *p1, *p2;17         ListNode *root, *t1, *t2;18         ListNode *par;19         20         root = new ListNode(0);21         root->next = head;22         p1 = root;23         for(i = 0; i < m - 1; ++i){24             p1 = p1->next;25         }26         // 1RE here, wrong pointer27         par = p1;28         p1 = p1->next;29         30         t1 = nullptr;31         t2 = p1;32         // 1RE here, i < n - m + 133         for(i = 0; i < n - m + 1; ++i){34             p2 = t2;35             p2 = p2->next;36             t2->next = t1;37             t1 = t2;38             // 1RE here, wrong pointer39             t2 = p2;40         }41         // 1WA, wrong pointer42         par->next = t1;43         p1->next = t2;44         head = root->next;45         46         delete root;47         return head;48     }49 };

Solution2:

　　In the solution above, one new operation was called. This overhead can be reduced with some extra code.

　　Always remember that new and delete are expensive operations, especially when they're called unnecessarily or irregularly.

　　Please see the code below. Time complexity is O(n), space complexity is O(1).

Accepted code:

1 // 1WA, 1AC, faulty operator is extremely difficult to debug, take this lesson! 2 /** 3  * Definition for singly-linked list. 4  * struct ListNode { 5  *     int val; 6  *     ListNode *next; 7  *     ListNode(int x) : val(x), next(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     ListNode *reverseBetween(ListNode *head, int m, int n) {13         // IMPORTANT: Please reset any member data you declared, as14         // the same Solution instance will be reused for each test case.15         int i;16         ListNode *p1, *p2;17         ListNode *t1, *t2;18         ListNode *par;19         20         // 1WA here, (O_o), != or ==? ...21         if(head == nullptr){22             return head;23         }24         25         if(m > 1){26             p1 = head;27             for(i = 0; i < m - 2; ++i){28                 p1 = p1->next;29             }30             par = p1;31             p1 = p1->next;32         }else{33             par = nullptr;34             p1 = head;35         }36         37         t1 = nullptr;38         t2 = p1;39         for(i = 0; i < n - m + 1; ++i){40             p2 = t2->next;41             t2->next = t1;42             t1 = t2;43             t2 = p2;44         }45         if(par != nullptr){46             par->next = t1;47         }else{48             head = t1;49         }50         p1->next = t2;51         52         return head;53     }54 };