Reverse Linked List in given Range m and n

PROBLEM :

 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.

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverse(struct ListNode *) ;

struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
   
    if(head==NULL||(m==n))
        return head ;
       
    struct ListNode *t1,*t2,*t3,*t4 ;
    int i=1 ;
    t1=head ;
   
    while(i!=m)
    {
        t1=t1->next ;
        i++ ;
    }
   
    i=1 ;
    t2=head ;
    while(i!=n)
    {
        t2=t2->next ;
        i++ ;
    }
   
    t3=t2->next ;
    t2->next=NULL ;
   
    t4=head  ;
    i=1 ;
    if(m!=1)
        while(i!=m-1)
        {
            t4=t4->next ;
            i++ ;
        }
    if(m==1)
    {
        head=reverse(t1) ;
        t1=head ;
        while(t1->next!=NULL)
            t1=t1->next ;
           
        t1->next=t3 ;
       
        return head ;
    }
    else
    {
        t4->next=reverse(t1) ;
        t1=t4 ;
        while(t1->next!=NULL)
            t1=t1->next ;
           
        t1->next=t3 ;
       
        return head ;
    }
}

struct ListNode* reverse(struct ListNode *head)
{
    if(head==NULL||head->next==NULL)
        return head ;
       
    struct ListNode *one,*two,*third ;
    one=head ;
    two=one->next ;
    third=two->next ;
   
    one->next=NULL ;
    two->next=one ;
   
    while(third!=NULL)
    {
        one=two ;
        two=third ;
        third=third->next ;
       
        two->next=one ;
    }
    return two ;
}

---------------------------------------------------------------------------------

Comments

Popular posts from this blog

Count ways to N'th Stair(Order does not matter)

Replace all ‘0’ with ‘5’ in an input Integer

Chocolate Distribution Problem

Remove characters from the first string which are present in the second string

Primality Test ( CodeChef Problem code: PRB01 )