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->NULLm = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

C++:
01 ListNode *reverseBetween(ListNode *head, int m, int n)
02  {
03         if(m==n)
04             return head;
05         if(head->next==NULL)
06             return head;
07         ListNode* tmp=head->next;
08         ListNode* prvm=head;
09         ListNode* mpt=head;
10         ListNode* prv=head;
11         ListNode* cur=tmp->next;
12         if(m==1){
13             for(int i=1;i<n;i++){
14                 tmp->next=prv;
15                 prv=tmp;
16                 tmp=cur;
17                 if(cur)
18                     cur=cur->next;
19             }
20             mpt->next=tmp;
21             return prv;
22         }
23         for(int i=1;i<m1;i++)
24             prvm=prvm->next;
25         mpt=prv=prvm->next;
26         tmp=prv->next;
27         cur=tmp->next;
28         for(int i=m;i<n;i++){
29             tmp->next=prv;
30             prv=tmp;
31             tmp=cur;
32             if(cur)
33               cur=cur->next;
34         }
35         prvm->next=prv;
36         mpt->next=tmp;
37         return head;
38 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s