C++实现反转链表_反转链表c++实现

        反转链表是数据结构里面一道很经典的题目，在秋招刷题时通常是广大同学们入门的第一题，具体反转前后链表的结构如下图所示：

对于反转链表通常有两组实现的方式，非递归法和递归法，具体的实现如下代码所示：

#include <iostream>
using namespace std;
 
struct ListNode
{
    int val;
    struct ListNode *next;
};
 
//1.非递归法反转链表
ListNode* reverseList(ListNode* head)
{
    ListNode *pre = NULL;
    ListNode *cur = head;
    ListNode *nex = NULL;
 
    while(cur)
    {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    return pre;
}
 
//2.递归反转链表
ListNode* reverseList2(ListNode* head)
{
    if(head == NULL || head->next == NULL)
        return head;
    ListNode *pNode = reverseList33(head->next);
    head->next->next = head;
    head->next = NULL;
    return pNode;
}