Leetcode：反轉鏈表
示列：輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
一、迭代方法反轉鏈表，
迭代是通過將1->2->3->4->5->NULL，一個個反轉得到NULL<-1<-2<-3<-4<-5;
在進行迭代時我們需要定義三個結構體指標： n1 (表示要反轉的前一個結點)，n2(表示要反轉的結點)，n3(表示要反轉的下一個結點)；
n1的存在是為了讓n2指向它，形成反轉，n3是為了保存下一個結點的地址，否則，當反轉一個后，鏈表會斷開，
畫圖理解一下：
代碼實作如下：
typedef struct ListNode Node;
struct ListNode* reverseList(struct ListNode* head){
if(head==NULL||head->next==NULL)//鏈表如果是一個或者NULL不用反轉，直接回傳，
{
return head;
}
Node*n1=NULL;//頭的前一個
Node*n2=head;//頭
Node*n3=head->next;//頭的下一個
while(n2)
{
//反轉，
n2->next=n1;//讓頭指向NULL
n1=n2;//向后走
n2=n3;
if(n3)//如果n3為空，n3就不能在想向后移動，
n3=n3->next;
}
return n1;
二、頭插，反轉鏈表，
先新定義一個結構體指標 頭（newHead）,保存鏈表的頭（cur）,保存鏈表的頭的下一個（next);
把鏈表從左到右 頭插到 新的頭 上；
如圖所示：
代碼如下：
typedef struct ListNode Node;
struct ListNode* reverseList(struct ListNode* head){
Node*cur=head;
Node*newHead=NULL;
while(cur)
{
Node*next=cur->next;//隨著cur向后走，next也在向后走，
//頭插cur當作新結點
cur->next=newHead;//頭插
newHead=cur;//更新頭
cur=next;//向后走
}
return newHead;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/235992.html
標籤：其他
下一篇：【解決方案】GB28181/RTSP/SDK/Ehome協議支持級聯視頻智能分析平臺EasyCVR搭建小區園區視頻監控系統