鏈表是編程學習的一個難點。其實，在C語言編程以及單片機裸機開發中，鏈表運用并不多。但是如果想提升嵌入式技能水平或收入水平，可以考慮深入嵌入式系統層面（如參與操作系統設計、深入學習新的操作系統等），此時，鏈表技術至關重要。

本期講解一道C語言的算法題——反轉一個單向鏈表。

題目描述：

已知鏈表的節點類型如下：

typedef struct node{

int data;

   struct node* next;

}Node;

現在有一條單鏈表，其節點類型為Node，鏈表的頭節點為head，請設計一種方法反轉該鏈表，并返回反轉后的鏈表。

Part 1

鏈表的基本介紹

Q1: 什么是節點？

A1: 節點是鏈表的構成單元，節點類型本質上是結構體類型，如題中出現的Node類型。正常情況下，一個節點至少包含兩個成員，一個成員保存該節點的數據，比如int data; 另一個成員是一個指針，比如Node *next，用于指向下一個節點。因此多個節點可以串在一起，構成鏈表。

Q2: 什么是鏈表？

A2: 百度百科中是這樣定義鏈表的。“鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。”

核心：鏈表是一種存儲結構。

可以將鏈表與數組進行對比，鏈表的優勢在于：對存儲單元進行插入/刪除操作更靈活方便（節點是鏈表的構成單元，元素是數組的構成單元）、鏈表的容量可以動態改變（而數組一旦定義，則容量固定，可能會有溢出風險）。

Q3: 鏈表的分類有哪些？

A3: 根據節點之間的關系，可以分為單鏈表（一般指單向不循環鏈表）、雙鏈表、循環單鏈表。

Part 2

解題思路

先確認下本題中的節點類型。

typedef struct node{

           int data;

           struct node* next;

    }Node;

由于本題采用一個單向不循環鏈表，鏈表的尾節點的指針成員指向NULL，可在示意圖中先補充地址NULL。

圖示的原鏈表由4個節點構成，分別是節點A、B、C和D，他們的data（數據成員）的值依次是1、2、3和4。節點A是首節點，即head保存節點A的地址。節點A的next（指針成員）指向節點B，節點B的next指向節點C，節點C的next指向節點D，節點D的next指向NULL。

觀察原鏈表和轉換后的圖示，可以看出轉換后節點之間的指向關系將完全反過來，節點D最終成為首節點，head將保存它的地址。

思考，得出以下結論：

1. 在單向鏈表中，若要遍歷節點，必須從鏈表首節點開始逐個訪問，所以反轉鏈表時，必須要按照原鏈表節點順序逐個操作。（即按照從節點A到節點D的順序）
2. 除了尾節點外，更改每個節點的next（指針成員）值之前，必須先用指針指向在原鏈表中該節點的下一個節點（比如：在更改節點A的next為NULL之前，必須用指針指向節點B，否則將丟失數據）。
3. head指針用于保存鏈表的首節點的地址，會隨著節點的反轉，逐漸移動（改變指向）。

Step1,定義兩個特殊用途的指針。

//指針p用于指向待反轉節點的前一個節點
Node *P = NULL;
//指針N用于指向待反轉節點的后一個節點
Node *N = head;
//本示例中head指針指向的節點也就是待操作的節點

Step2,用指針N指向待操作節點的下一個節點，反轉一個節點（改變待操作節點的next成員）。

N = N- >next;
head- >next = P;

Step3,準備反轉下個節點前，需要依次改變P指針和head指針。

P = head;
head = N;

Step4,用指針N指向待操作節點的下一個節點，反轉一個節點（改變待操作節點的next成員）。

此步驟和Step2相同，已開始重復的操作了。故之后的步驟將省略。

需要注意的是，當head指針在某次偏移之后，它將會指向原鏈表的尾節點（此時head->next == NULL為真），就說明此刻僅需要反轉最后一個節點。

Part 3

示例代碼

示例說明：

為了方便演示運行效果，將在主函數中構建4個Node類型的結構體變量，先對他們賦值，然后將他們串成鏈表，遍歷鏈表，打印節點數據（預期打印：1，2，3，4）。之后反轉鏈表，再次遍歷鏈表，打印節點數據（預期打印：4，3，2，1）。

核心代碼：鏈表反轉函數

Node *list_reverse(Node *head)
{
  Node *i;
  Node *P = NULL;
  Node *N = head;
  if(head == NULL)
    return NULL;

  while(head- >next != NULL) //判斷head是否為尾節點 
  {
    N = N- >next;
    head- >next = P;
    P = head;
    head = N;
  }
  head- >next = P; //反轉最后一個節點 

  return head; 
}

主程序設計

int main(void)
{
  Node A,B,C,D;
  //分別對4個節點的data賦值，并將他們串成鏈表 
  A.data = 1; A.next = &B;
  B.data = 2; B.next = &C;
  C.data = 3; C.next = &D; 
  D.data = 4; D.next = NULL;
  Node *head = &A;
  
  printf("原鏈表：\\n");
  list_output(head);
  head = list_reverse(head);
  printf("\\n反轉后：\\n");
  list_output(head);
  return 0;
}

運行結果

和預期一致，代碼驗證成功！