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->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.
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:

  1. Code(updated 201309)还可以再优化一下,k1,k2每次都是从0跑到m+i, n-i, 如果先跑到m结点,从这儿开始算,两个游标每次跑的距离就会缩短m。

    ReplyDelete
    Replies
    1. Yes, of course it can be done like you said (see my old version code), it is slight complex and need to be careful with the subscript. Thus, I post the newer version which is more straightforward.

      Thanks for you comment!

      Delete
  2. 楼主你后来的那个版本通不过OJ....

    ReplyDelete
    Replies
    1. Oh, thank you very much for your reply!
      I've checked the code, it seems the line 15, m-n should be n-m.

      Delete
  3. 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.

    ReplyDelete
  4. Use one deque to store the ListNodes from m to n just for one pass, and then do the swap on the deque

    ReplyDelete
  5. This is not an efficient solution since you are going from the head to k1 and k2 position in each iteration.

    ReplyDelete
  6. 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;
    }
    };

    ReplyDelete
  7. 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;

    }
    };

    ReplyDelete