Yu's Coding Garden : leetcode Question 85: Reverse Linked List II

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.

Analysis:

In this problem, do not think it too hard, reverse the linked list here is just reverse the value of node.
So the idea is to scan the linked list once, if not meet the reverse sublist, keep going, if reverse done(here the position is the middle of the sublist which needed to be reversed), return, because the latter list do not need any change. While in the sublist, for each element, (1)find the node to be swapped, (2) swap the values.
In the code below, note that,
(1) the stop condition is the middle of the reversed sublist (m+(n-m)/2)
(2) for each element in the sublist, the swapping element is the next (n-m-(i-m)*2) element.
e.g.
1-2-3-4-5-6-7-8-9-10-null
| |
m=2 n=9
for 2, just get the next (n-m) element.

1-9-3-4-5-6-7-8-2-10-null
| |
i=3 idx=8

next element 3, the swapping element is 8.

Code(updated 201309):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode* h=head;
        for (int i=0;i<n-m;i++){
            int k1=m+i;
            int k2=n-i;
            if (k1>=k2){return head;}
            ListNode* p = h;
            ListNode* q = h;
            while (k1-1>0){p=p->next;k1--;}
            while (k2-1>0){q=q->next;k2--;}
            int tmp=p->val;
            p->val=q->val;
            q->val=tmp;
        }
        return head;
    }
};

Code(old version):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode* p=head;
        int i=1;
        while (p!=NULL){
            if (i>(m+int((n-m)/2))) {return head;}
            if (i<m) {i++;p=p->next;}
            else{
                ListNode* q = p;
                for (int j=0;j<(n-m-(i-m)*2);j++){
                    q=q->next;
                }
                int tmp = p->val;
                p->val = q->val;
                q->val=tmp;
                i++;
                p=p->next;
            }
        }
        return head;
    }
};

9 comments:

UnknownSeptember 9, 2013 at 7:28 AM
Code(updated 201309)还可以再优化一下，k1,k2每次都是从0跑到m+i, n-i, 如果先跑到m结点，从这儿开始算，两个游标每次跑的距离就会缩短m。
UnknownOctober 30, 2013 at 4:20 PM
楼主你后来的那个版本通不过OJ....
UnknownDecember 28, 2013 at 7:00 PM
Hey man, you can also do it by manipulating the pointers instead of swapping the values of each node. In fact, I prefer using the pointers, cause I think that's the original purpose of this problem.
UnknownApril 2, 2014 at 6:59 PM
Use one deque to store the ListNodes from m to n just for one pass, and then do the swap on the deque
GaganpreetAugust 23, 2014 at 2:26 AM
This is not an efficient solution since you are going from the head to k1 and k2 position in each iteration.
UnknownAugust 15, 2016 at 12:44 PM
A bit better:
class Solution {
public:
int getCount(ListNode *head)
{
if(head==NULL) return 0;
return 1+getCount(head->next);
}
ListNode* reverseKGroup(ListNode* head, int k) {
if(head==NULL) return NULL;
ListNode *cur=head,*prev=NULL,*temp;
int count=0;
int size=getCount(head);
if(sizenext;
cur->next=prev;
prev=cur;
cur=temp;
count++;
}

head->next=reverseKGroup(cur,k);
return prev;
}
};
UnknownAugust 15, 2016 at 1:21 PM
Above code was for a different question.
The right solution is below:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n)
{
if(head==NULL||head->next==NULL||m==n) return head;
ListNode *cur=head,*prev=NULL,*temp,*first,*slast;
int count=0;
for(int i=0;inext;
}
first=prev;
slast=cur;
while(cur&&count<=(n-m))
{
temp=cur->next;
cur->next=prev;
prev=cur;
cur=temp;
count++;
}
ListNode *second=prev,*last=cur;
if(first!=NULL)
first->next=second;
slast->next=last;

if(m!=1)
return head;
else
return second;

}
};