樣例
給出一個鏈表1->2->3->null，這個翻轉(zhuǎn)后的鏈表為3->2->1->null
復(fù)制鏈表節(jié)點(diǎn)局雄，一個一個放入新鏈表
新建一個鏈表街州，記錄表頭刑顺，每次把新的節(jié)點(diǎn)插入到表頭位置。這樣就要建立一個假節(jié)點(diǎn)指向表頭缔杉。
ListNode * reverse(ListNode * head)
{
if(head==NULL)
return NULL;
ListNode *lastNode=new ListNode(head->val);
ListNode *new_head=new ListNode(0); //新的鏈表的假表頭
new_head->next=lastNode; //第一個數(shù)作為最后一個節(jié)點(diǎn)
while(head->next!=NULL)
{
head=head->next;
ListNode *temp=new ListNode(head->val); //復(fù)制這樣的節(jié)點(diǎn)值
temp->next=new_head->next;
new_head->next=temp; //把這個節(jié)點(diǎn)插入到新鏈表中
}
return new_head->next;
}
不新建鏈表锤躁，通過指針操作
每次把head后面的一個節(jié)點(diǎn)翻轉(zhuǎn)到head的前面。是下面這個過程或详。
1-2-3-4-5
2-1-3-4-5
3-2-1-4-5
4-3-2-1-5
5-4-3-2-1
經(jīng)過5次操作就可以了系羞，依然是要建立一個假表頭。這個假表頭指向head霸琴，head本身是不動的椒振，但是head后面的一個元素相當(dāng)于刪除掉了。
head后面的這個稱作temp梧乘，每次循環(huán)做兩個操作：
- temp前后鏈接起來澎迎，即把head和temp后面的鏈接起來。
- 把temp插入到假表頭的后面选调。
這樣寫出來的竟然是頂針的夹供，還是挺好看的。
寫鏈表的題一定慎重修改指針仁堪。
ListNode * reverse(ListNode * head)
{
if(head==NULL)
{
return NULL;
}
ListNode *new_head=new ListNode(0); //新建一個假的節(jié)點(diǎn)指向表頭
ListNode *temp; //需要拿出來放入new_head后面的節(jié)點(diǎn)
//head本身是不變的哮洽，只是head指向的下一個會變，相當(dāng)于把中間拿出來放到head的前面了
new_head->next=head;
while(head->next!=NULL)
{
temp=head->next;
head->next=temp->next; //鏈接起來temp前后
temp->next=new_head->next; //把temp插入到res后面
new_head->next=temp;
}
return new_head->next;
}
