描述

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

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

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


这是第一次实现的代码（很挫—_—）

typedefstructListNode{int_var;structListNode*_next;ListNode(intvar):_var(var),_next(NULL){}}node,*node_p;classSolution{public:node_pReserveList(node_p&head,intm,intn){//检查边界条件if(head==NULL){printf("ListisNULL\n");returnNULL;}if(m<1||n<m){//未检查n的边界printf("rangleiserror\n");returnNULL;}if(n==m)returnhead;//******************node_pprev=head;node_pa=head;node_pb=head;for(inti=2;i<m;++i){prev=prev->_next;}for(inti=1;i<m;++i){a=a->_next;}for(inti=1;i<n;++i){b=b->_next;}node_ptmp=newnode(-1);//a->_next=b->_next;node_plast=a;while(a!=b){if(m==1)prev=prev->_next;elseprev->_next=a->_next;a->_next=tmp->_next;tmp->_next=a;if(m==1)a=prev;elsea=prev->_next;}if(m==1){prev=b->_next;b->_next=tmp->_next;tmp->_next=b;last->_next=prev;node_pNewhead=tmp->_next;free(tmp);returnNewhead;}prev->_next=b->_next;b->_next=tmp->_next;tmp->_next=b;last->_next=prev->_next;prev->_next=tmp->_next;free(tmp);returnhead;}};

这是重新写的代码（还是很挫,感觉整个人都不好了）

reverse_linklist.h:

#pragmaonce#include<iostream>#include<assert.h>#include<stdlib.h>usingnamespacestd;typedefstructListNode{int_var;ListNode*_next;ListNode(intvar):_var(var),_next(NULL){}}node,*node_p;classSolution{public:node_preverse_link(node_p&list,intm,intn){//边界检查if(list==NULL)returnNULL;if(m<1||m>n){cout<<"parametererror"<<endl;returnNULL;}if(m==n)returnlist;nodedummy(-1);node_phead=&dummy;head->_next=list;for(inti=0;i<m-1;++i){head=head->_next;}node_pfirst=list;for(inti=1;i<m;++i)first=first->_next;node_psecond=first;for(inti=m;i<n;++i)second=second->_next;node_ptmp=first;//核心步骤while(tmp!=second){tmp=first->_next;first->_next=tmp->_next;tmp->_next=head->_next;head->_next=tmp;}if(m==1)returnhead->_next;returnlist;}};

test.cpp

#include"reverse_linklist.h"usingnamespacestd;intmain(){node_pn1=newnode(1);node_pn2=newnode(2);node_pn3=newnode(3);node_pn4=newnode(4);node_pn5=newnode(5);n1->_next=n2;n2->_next=n3;n3->_next=n4;n4->_next=n5;Solutions;node_pnewhead=s.reverse_link(n1,3,5);while(newhead!=NULL){node_ptmp=newhead;cout<<tmp->_var<<"";newhead=newhead->_next;free(tmp);}cout<<endl;return0;}

运行结果：



还是来看看人家的代码吧：

自己还是弱的很，需要更努力啦^_^


《完》