逆轉單向鏈表的意思是：給定你一個單向鏈表，一個整數n（n為要逆轉的結點數），要求你把鏈表從頭結點到第n個結點給逆轉過來
圖示：
給出一個單向鏈表，一個整數n=4。也就是要求把該鏈表從頭結點（head->next）開始到第四個結點，把他們逆轉過來。逆轉后頭結點由1變成了4，然后1來鏈接5

那么如何實現這樣的逆轉鏈表呢？既然要改變結點的序列，我們自然而然想到要用一些指針來指向保存這些結點。這里用到三個指針：New,Old,Tag

New指針：所指的就是完成逆轉的鏈表的頭結點
Old指針：所指的就是未完成逆轉的鏈表的頭結點
Tag指針；指向Old的下一個結點

一開始的時候可以先讓New指向鏈表的頭結點，讓Old指向New的下一個結點

為什么要用Tag呢？（參照上圖）當我們把2這個結點的next逆轉向1后，2后的鏈表就找不回來了。所以Tag是用來保存逆轉過程中Old后的結點，為了在Old逆轉后，開始下一個結點的逆轉時還能找回Old的下一個結點進行逆轉

三個指針設定好后，接下來就可以開始逆轉鏈表了。首先我們把2這個結點的next逆轉過來指向1，然后把三個指針都依次向后移動一個結點。New指向了2結點，New所指的就是完成逆轉的鏈表的頭結點，Old指向3，Old指向了當前還沒完成逆轉的鏈表的頭結點，Tag指向Old的下一個結點
接下來繼續逆轉，下一步就是把Old所指的未完成逆轉的結點進行逆轉，也就是把3->next指向2，然后三個指針New，Old，Tag依次往后移一位
當逆轉的結點到了第4個結點后（到達給定的整數n），也就是應該停止不需要再往后逆轉了。這時，我們看看還需要什么改動：1這個結點的指向還是指向2，1這個結點應該指向n+1這個結點，也就是逆轉前的第n個結點（或者說逆轉完后的頭結點）的下一個結點，這個結點我們用Tag保存了起來。所以我們要做的下一步就是把1這個逆轉完后的尾結點的next指向Tag，也就是4這個結點。然后鏈表的head結點此時也要做修改，不是指向1這個結點了，而是指向逆轉完后的頭結點（也就是New這個結點）
這樣我們就完成了對單向鏈表的n個結點的逆轉。
如下是代碼實現：

List Reserve(List head,int n) {int cnt=1;List New,Old,Tag;New=Head->next;Old=New->next;while(cnt<n){Tag=Old->next;Old->next=New;New=Old;Old=Tag;cnt++;}Head->next->next=Old;return New; }

1.傳進去的兩個參數：鏈表的頭結點head，整數n
定義三個指針New，Old，Tag
定義cnt做計數

2.開始讓New指針指向頭結點（head->next）
讓Old指向New->next

3.然后開始做逆轉
while循環在cnt<n（也就是還沒逆轉完）時進行
循環里：先讓Tag指針指向Old->next(保存Old的下一個結點的位置)
然后做逆轉，逆轉一次cnt++
逆轉完之后把New，Old指針向后移

4.當完成了n個結點的逆轉后
跳出循環做最后兩步
首先頭結點head->next->next指向Old結點（也就是逆轉前的頭結點）
之后把頭結點return出去賦給head就可以了

總結

以上是生活随笔為你收集整理的单向链表的逆转（数据结构)（c语言）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。