鏈表反轉是學習鏈表中必不可免會碰到的問題碎连，熟練掌握、精準分析有助于對鏈表更深一步的理解

第一種思路：非遞歸思路

image.png

#include <iostream>
using namespace std;
struct LinkedListNode{
    int value;
    LinkedListNode *next;
};
//創(chuàng)建結點 注意&
void createNode(LinkedListNode * & head,int num){
    //創(chuàng)建新結點
    LinkedListNode *newNode = (LinkedListNode *)malloc(sizeof(LinkedListNode));
    newNode ->value = num;
    newNode ->next = NULL;
    if (head == NULL) {
        head = newNode;
        return;
    }
    newNode -> next = head;
    head = newNode;
    
}
//結點數(shù)據(jù)輸出展示
void printNumOfNode(LinkedListNode *head){
    LinkedListNode *node = head;
    while (node != NULL) {
        cout<<node->value<<"  ";
        node = node ->next;
    }
    cout<<endl;
}
LinkedListNode* reverseLinkedListNode(LinkedListNode *head){
    //注意邊界值 保證數(shù)據(jù)的完整性
    if (head == NULL || head ->next == NULL) {
        return head;
    }
    LinkedListNode *preNode = head;//當前結點的前一個結點
    LinkedListNode *curNode = head -> next;//當前結點
    LinkedListNode *nextNode= curNode ->next;//當前結點的后一個結點
    
    while (curNode != NULL ) {//當前不為空躏精，也就是說當前結點不是尾結點的時候
        nextNode = curNode -> next;//先保留當前結點的下一個結點【因為當前結點next更改后形成了“斷鏈”】
        curNode -> next = preNode;//將當前結點指向當前結點的前一個結點 此時該結點指向完成
        preNode = curNode;//將當前結點的前一個結點指針后移渣刷，為下一個結點比較做準備
        curNode = nextNode;//下一個結點就順利成長的變?yōu)榱水斍敖Y點，依次比較下去
    }
    head -> next = NULL;//此時反轉結束矗烛，需要將反轉后鏈表的最后一個即鏈表反轉前的第一個結點的next置為NULL保證單鏈表的完整性
    return preNode;//此時反轉后的preNode也是curNode就是反轉后鏈表的第一個結點辅柴，串聯(lián)起整個單鏈表
}
int main(int argc, const char * argv[]) {
    LinkedListNode *head = NULL;
    for (int i= 0; i<8; i++) {
        createNode(head, i+1);
    }
    printNumOfNode(head);//反轉前鏈表value展示
    //反轉函數(shù)
    head = reverseLinkedListNode(head);
    printNumOfNode(head);//反轉后鏈表value展示
    return 0;
}

第二種思路：遞歸思路

LinkedListNode * ReverseList(LinkedListNode * head)
{
    //遞歸終止條件：找到鏈表最后一個結點
    if (head == NULL || head-> next == NULL)
        return head;
    else
    {
        LinkedListNode * newhead = ReverseList(head->next);//先反轉后面的鏈表，從最后面的兩個結點開始反轉瞭吃，依次向前
        head->next->next = head;//將后一個鏈表結點指向前一個結點
        head->next = NULL;//將原鏈表中前一個結點指向后一個結點的指向關系斷開
        return newhead;
    }
}

【思路碌嘀、實現(xiàn)詳情見代碼注釋】