剑指offer_面试题16_反转链表（两种方法）

蔚落 2022-08-03 14:46 176阅读 0赞

**题目：**定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

**在解决问题前，先想好测试用例：**

**1、功能测试：**输入的链表含有多个结点，链表中只有一个结点

**2、特殊输入测试：**头结点为 NULL指针

**解决这个问题有两种方式：**

**前提：**

**这两种方式 是以 头结点并不是第一个数据节点 为基准 表示的。**

**这种方式，头结点并不保存链表的结点数据，其数据位只保存链表结点总数。**

**在输出链表时，从头结点后的第一个数据结点开始输出，并不输出头结点。**

**方法：**

**1、头插法：**将头结点后的链中结点 从前向后一个个断开，并依次以头插法插入在头结点后，这样也相当于完成了链表的反转，链表的头结点依然是原头结点。

**2、逆转指针：**即书上所阐述的方法。这种方法比较直观，将每个结点的指向翻转过来，原来指向后一结点的，现在指向前一个结点。

对于第二种方法，可以对照下图来理解：

图中阐述了一般情况下，即在链表中间，反转一个结点的步骤。其他结点反转的方式相同。

![20150810104531702][]

**算法如下：**

#include <iostream>
    
    using namespace std;
    
    typedef struct Node{
        int m_nValue;
        struct Node *m_pNext;
    }ListNode;
    
    /**创建空链表*/
    ListNode * creat_List()
    {
        ListNode *pHead;
        pHead = new ListNode;
        pHead->m_nValue = 0;    /**头结点中保存数据节点总数*/
        pHead->m_pNext = NULL;
    
        return pHead;
    }
    
    /**在链表最后插入节点*/
    ListNode * insert_Node_behind(ListNode *pHead,int pElem)
    {
        if(NULL == pHead)
        {
            cout << "头结点为空" << endl;
            return pHead;
        }
    
        ListNode *temp, *current;
        current = pHead;
        while(NULL != current->m_pNext)
        {
            current = current->m_pNext;
        }
        temp = new ListNode;
        temp->m_nValue = pElem;
        temp->m_pNext = NULL;
        current->m_pNext = temp;
    
        pHead->m_nValue += 1;
    
        return pHead;
    }
    
    /**遍历输出链表*/
    void show_List(ListNode *pHead)
    {
        if(NULL == pHead)
        {
            cout << "头结点为空" << endl;
            return;
        }
        ListNode *temp;
        temp = pHead->m_pNext;
    
        cout << "该 list 为：" ;
        while(NULL != temp)
        {
            cout << temp->m_nValue << ' ';
            temp = temp->m_pNext;
        }
        cout << endl;
    }
    
    /**方法一：将头结点后的链表，一个个断开，以从前往后的方式，用头插法依次接在头结点后*/
    ListNode * reverse_List_1(ListNode *pHead)
    {
        if(NULL == pHead || NULL == pHead->m_pNext)
        {
            return pHead;
        }
    
        ListNode *temp, *current;
        current  = pHead->m_pNext;
        pHead->m_pNext = NULL;      /**头结点和后面的结点断开*/
    
        while(NULL != current)
        {
            temp = current->m_pNext;
            current->m_pNext = pHead->m_pNext;
            pHead->m_pNext = current;
            current = temp;
        }
        return pHead;
    }
    
    /**方法二，改变指针方向*/
    ListNode *reverse_List_2(ListNode *pHead)
    {
        if(NULL == pHead || NULL == pHead->m_pNext)
        {
            return pHead;
        }
    
        ListNode *pPre, *pCurr, *pNex;
        //ListNode *temp = pHead;
    
        /**设定三个指针的初始状态*/
        pCurr = pHead->m_pNext;    /**保存当前结点*/
        pNex = pCurr->m_pNext;     /**保存当前结点的下一结点*/
        pPre = NULL;               /**保存当前结点的前一结点*/
    
        //pHead->m_pNext = NULL;
        //pHead = NULL;
    
    
        while(NULL != pNex)
        {
            pCurr->m_pNext = pPre; /*反转步骤*/
    
            pPre = pCurr;          /*更新步骤*/
            pCurr = pNex;
            pNex = pNex->m_pNext;
        }
    
        pCurr->m_pNext = pPre;       /*将最后一个节点指向它的前一结点，防止链表断裂*/
        /** pNex = pPre;   pCurr->m_pNext 和 pNex 虽然指的位置相同，但是并不是同一个指针，如果这样写会连接不起来 */
        pHead->m_pNext = pCurr;      /**将倒序后的结点链表，从新接头结点后，这样反转后的头结点依然是原来的头结点，而第一个数据结点则变成了原来的尾结点*/
    
        return pHead;
    }
    
    int main()
    {
        int n_of_list = 6;
        int i = 1;
        ListNode *pHead;
        pHead = creat_List();
        while(n_of_list > 0)
        {
            insert_Node_behind(pHead,i++);
            n_of_list--;
        }
        show_List(pHead);
    
        reverse_List_1(pHead);
        show_List(pHead);
    
        reverse_List_2(pHead);
        show_List(pHead);
        
        return 0;
    }

**结果如下：**

以下是链表多结点情况，对于其他情况的测试（如单个结点，NULL指针等），可以改变代码中的数据，来测试。

![20150810105328288][]

/\*点滴积累，我的一小步O(∩\_∩)O~\*/

[20150810104531702]: /images/20220731/9ee9e8a39d714f48a2d1278e659267fe.png
[20150810105328288]: /images/20220731/3e0c8cdb50fb4011abeb9a37514a83f4.png