チェーンテーブルの反転とチェーンテーブルの一部の反転
チェーンテーブルの反転
チェーンテーブルの一部を反転
#include
using namespace std;
struct ListNode{
int val;
ListNode *next;
};
ListNode* reverse(ListNode* head){
ListNode *new_head=NULL;
while(head){
ListNode* next=head->next;
head->next=new_head;
new_head=head;
head=next;
}
return new_head;
}
int main() {
ListNode a;
ListNode b;
ListNode c;
ListNode d;
cout<<"next:"<<b.next<<endl;
a.val=1;
b.val=2;
c.val=3;
d.val=4;
a.next=&b;
b.next=&c;
c.next=&d;
d.next=NULL;
ListNode *head=&a;
while(head){
cout<<head->val<<endl;
head=head->next;
}
head=&a;
ListNode* new_head=reverse(head);
cout<<" "<<endl;
while(new_head){
cout<<new_head->val<<endl;
new_head=new_head->next;
}
return 0;
}
チェーンテーブルの一部を反転
#include
using namespace std;
struct ListNode{
int val;
ListNode* next;
};
ListNode* reverseBetween(ListNode* head,int m,int n){
int change_len=n-m+1;
ListNode* pre_head=NULL;
ListNode* reuslt=head;
while(head&&--m){
pre_head=head;
head=head->next;
}
ListNode* modified_list_tail=head;
ListNode* new_head=NULL;
while(head&& change_len){
ListNode* next=head->next;
head->next=new_head;
new_head=head;
head=next;
--change_len;//change_len--;
}
modified_list_tail->next=head;
if (pre_head){
pre_head->next=new_head;
}else{
reuslt=new_head;
}
return reuslt;
}
int main() {
ListNode a;
ListNode b;
ListNode c;
ListNode d;
ListNode e;
ListNode f;
ListNode g;
ListNode h;
a.val=1;
b.val=2;
c.val=3;
d.val=4;
e.val=5;
f.val=6;
g.val=7;
h.val=8;
a.next=&b;
b.next=&c;
c.next=&d;
d.next=&e;
e.next=&f;
f.next=&g;
g.next=&h;
h.next=NULL;
ListNode* head=&a;
while(head){
cout<<head->val<<endl;
head=head->next;
}
head=&a;
ListNode* reuslt=reverseBetween(head,3,7);
while(reuslt){
cout<<reuslt->val<<endl;
reuslt=reuslt->next;
}
}