链表运用---反转链表（二）

链表反转是学习链表中必不可免会碰到的问题，熟练掌握、精准分析有助于对链表更深一步的理解

第一种思路：非递归思路

image.png

#include <iostream>
using namespace std;
struct LinkedListNode{
    int value;
    LinkedListNode *next;
};
//创建结点 注意&
void createNode(LinkedListNode * & head,int num){
    //创建新结点
    LinkedListNode *newNode = (LinkedListNode *)malloc(sizeof(LinkedListNode));
    newNode ->value = num;
    newNode ->next = NULL;
    if (head == NULL) {
        head = newNode;
        return;
    }
    newNode -> next = head;
    head = newNode;
    
}
//结点数据输出展示
void printNumOfNode(LinkedListNode *head){
    LinkedListNode *node = head;
    while (node != NULL) {
        cout<<node->value<<"  ";
        node = node ->next;
    }
    cout<<endl;
}
LinkedListNode* reverseLinkedListNode(LinkedListNode *head){
    //注意边界值 保证数据的完整性
    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;//下一个结点就顺利成长的变为了当前结点，依次比较下去
    }
    head -> next = NULL;//此时反转结束，需要将反转后链表的最后一个即链表反转前的第一个结点的next置为NULL保证单链表的完整性
    return preNode;//此时反转后的preNode也是curNode就是反转后链表的第一个结点，串联起整个单链表
}
int main(int argc, const char * argv[]) {
    LinkedListNode *head = NULL;
    for (int i= 0; i<8; i++) {
        createNode(head, i+1);
    }
    printNumOfNode(head);//反转前链表value展示
    //反转函数
    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;
    }
}

【思路、实现详情见代码注释】