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 ;
}
---------------------------------------------------------------------------------
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
Post a Comment