C語言算法題：反轉(zhuǎn)一個單向鏈表

鏈表是編程學(xué)習(xí)的一個難點(diǎn)。其實(shí)，在C語言編程以及單片機(jī)裸機(jī)開發(fā)中，鏈表運(yùn)用并不多。但是如果想提升嵌入式技能水平或收入水平，可以考慮深入嵌入式系統(tǒng)層面（如參與操作系統(tǒng)設(shè)計(jì)、深入學(xué)習(xí)新的操作系統(tǒng)等），此時，鏈表技術(shù)至關(guān)重要。

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

題目描述：

已知鏈表的節(jié)點(diǎn)類型如下：

typedef struct node{

int data;

   struct node* next;

}Node;

現(xiàn)在有一條單鏈表，其節(jié)點(diǎn)類型為Node，鏈表的頭節(jié)點(diǎn)為head，請?jiān)O(shè)計(jì)一種方法反轉(zhuǎn)該鏈表，并返回反轉(zhuǎn)后的鏈表。

Part 1

鏈表的基本介紹

Q1: 什么是節(jié)點(diǎn)？

A1: 節(jié)點(diǎn)是鏈表的構(gòu)成單元，節(jié)點(diǎn)類型本質(zhì)上是結(jié)構(gòu)體類型，如題中出現(xiàn)的Node類型。正常情況下，一個節(jié)點(diǎn)至少包含兩個成員，一個成員保存該節(jié)點(diǎn)的數(shù)據(jù)，比如int data; 另一個成員是一個指針，比如Node *next，用于指向下一個節(jié)點(diǎn)。因此多個節(jié)點(diǎn)可以串在一起，構(gòu)成鏈表。

Q2: 什么是鏈表？

A2: 百度百科中是這樣定義鏈表的。“鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的?！?/p>

核心：鏈表是一種存儲結(jié)構(gòu)。

可以將鏈表與數(shù)組進(jìn)行對比，鏈表的優(yōu)勢在于：對存儲單元進(jìn)行插入/刪除操作更靈活方便（節(jié)點(diǎn)是鏈表的構(gòu)成單元，元素是數(shù)組的構(gòu)成單元）、鏈表的容量可以動態(tài)改變（而數(shù)組一旦定義，則容量固定，可能會有溢出風(fēng)險）。

Q3: 鏈表的分類有哪些？

A3: 根據(jù)節(jié)點(diǎn)之間的關(guān)系，可以分為單鏈表（一般指單向不循環(huán)鏈表）、雙鏈表、循環(huán)單鏈表。

Part 2

解題思路

先確認(rèn)下本題中的節(jié)點(diǎn)類型。

typedef struct node{

           int data;

           struct node* next;

    }Node;

由于本題采用一個單向不循環(huán)鏈表，鏈表的尾節(jié)點(diǎn)的指針成員指向NULL，可在示意圖中先補(bǔ)充地址NULL。

圖示的原鏈表由4個節(jié)點(diǎn)構(gòu)成，分別是節(jié)點(diǎn)A、B、C和D，他們的data（數(shù)據(jù)成員）的值依次是1、2、3和4。節(jié)點(diǎn)A是首節(jié)點(diǎn)，即head保存節(jié)點(diǎn)A的地址。節(jié)點(diǎn)A的next（指針成員）指向節(jié)點(diǎn)B，節(jié)點(diǎn)B的next指向節(jié)點(diǎn)C，節(jié)點(diǎn)C的next指向節(jié)點(diǎn)D，節(jié)點(diǎn)D的next指向NULL。

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

思考，得出以下結(jié)論：

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

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

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

Step2,用指針N指向待操作節(jié)點(diǎn)的下一個節(jié)點(diǎn)，反轉(zhuǎn)一個節(jié)點(diǎn)（改變待操作節(jié)點(diǎn)的next成員）。

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

Step3,準(zhǔn)備反轉(zhuǎn)下個節(jié)點(diǎn)前，需要依次改變P指針和head指針。

P = head;
head = N;

Step4,用指針N指向待操作節(jié)點(diǎn)的下一個節(jié)點(diǎn)，反轉(zhuǎn)一個節(jié)點(diǎn)（改變待操作節(jié)點(diǎn)的next成員）。

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

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

Part 3

示例代碼

示例說明：

為了方便演示運(yùn)行效果，將在主函數(shù)中構(gòu)建4個Node類型的結(jié)構(gòu)體變量，先對他們賦值，然后將他們串成鏈表，遍歷鏈表，打印節(jié)點(diǎn)數(shù)據(jù)（預(yù)期打?。?，2，3，4）。之后反轉(zhuǎn)鏈表，再次遍歷鏈表，打印節(jié)點(diǎn)數(shù)據(jù)（預(yù)期打印：4，3，2，1）。

核心代碼：鏈表反轉(zhuǎn)函數(shù)

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

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

  return head; 
}

主程序設(shè)計(jì)

int main(void)
{
  Node A,B,C,D;
  //分別對4個節(jié)點(diǎn)的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反轉(zhuǎn)后：\\n");
  list_output(head);
  return 0;
}

運(yùn)行結(jié)果

和預(yù)期一致，代碼驗(yàn)證成功！