反轉單鏈表的幾種方法

題目：輸入一個鏈表的頭結點，反轉該鏈表，並返回反轉後鏈表的頭結點。鏈表結點定義如下：

struct ListNode
{
      int       m_nKey;
      ListNode* m_pNext;
};

分析：這是一道廣為流傳的微軟面試題。由於這道題能夠很好的反應出程序員思維是否嚴密，在微軟之後已經有很多公司在面試時采用了這道題。

為了正確地反轉一個鏈表，需要調整指針的指向。與指針操作相關代碼總是容易出錯的，因此最好在動手寫程序之前作全面的分析。在面試的時候不急於動手而是一開始做仔細的分析和設計，將會給面試官留下很好的印象，因為在實際的軟件開發中，設計的時間總是比寫代碼的時間長。與其很快地寫出一段漏洞百出的代碼，遠不如用較多的時間寫出一段健壯的代碼。

最容易想到的第一種方法就是重新建立一個單鏈表newList，每次將list中的第一個結點放到newList後面。注釋比較詳細，所以就不具體說了，直接看代碼吧：

LinkedList ReverseSinglyLinkedList(LinkedList list)
{
    LinkedList  newList;    //新鏈表的頭結點
    LNode       *tmp;       //指向list的第一個結點，也就是要摘除的結點
                           
    //
    //參數為空或者內存分配失敗則返回NULL
    //
    if (list == NULL || (newList = (LinkedList)malloc(sizeof(LNode))) == NULL)
    {
        return NULL;
    }
                           
    //
    //初始化newList
    //
    newList->data = list->data;
    newList->next = NULL;
                           
    //
    //依次將list的第一個結點放到newList的第一個結點位置
    //
    while (list->next != NULL)
    {
        tmp = newList->next;         //保存newList中的後續結點
        newList->next = list->next;       //將list的第一個結點放到newList中
        list->next = list->next->next;     //從list中摘除這個結點
        newList->next->next = tmp;        //恢復newList中後續結點的指針
    }
                           
    //
    //原頭結點應該釋放掉，並返回新頭結點的指針
    //
    free(list);
    return newList;
}

第二種方法是每次都將原第一個結點之後的那個結點放在list後面，下圖是原始的單鏈表。

為了反轉這個單鏈表，我們先讓頭結點的next域指向結點2，再讓結點1的next域指向結點3，最後將結點2的next域指向結點1，就完成了第一次交換，順序就變成了Header-結點2-結點1-結點3-結點4-NULL，然後進行相同的交換將結點3移動到結點2的前面，然後再將結點4移動到結點3的前面就完成了反轉，思路有了，就該寫代碼了：

LinkedList ReverseSinglyLinkedList(LinkedList list)
{
    LNode   *tmp = NULL;
    LNode   *p = NULL;
          
    if (list == NULL)
    {
        return NULL;
    }
    tmp = list->next;
    while (tmp->next != NULL)
    {
        p = tmp->next;
        tmp->next = p->next;
        p->next = list->next;
        list->next = p;
    }
    return list;
}

第三種方法跟第二種方法差不多，第二種方法是將後面的結點向前移動到頭結點的後面，第三種方法是將前面的結點移動到原來的最後一個結點的後面，思路跟第二種方法差不多，就不貼代碼了。

本文出自 “驿落黃昏” 博客，請務必保留此出處http://yiluohuanghun.blog.51cto.com/3407300/1305094