#AcWing 35.反转链表

题目

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

思考题：

• 请同时实现迭代版本和递归版本。

数据范围

链表长度 [0,30]。

样例

输入:1->2->3->4->5->NULL
 
输出:5->4->3->2->1->NULL

算法一：迭代

引用3个指针，踩砖迭代到cur为空。

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre=NULL;
        ListNode *cur=head;
        ListNode *next=NULL;
        while(cur){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
    
    
};

算法二： 递归

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    
    return newHead;

这段代码是使用递归来反转链表的函数reverseList。

首先，函数会检查传入的头结点head是否为空或者只有一个节点，如果是，则直接返回该头结点。

然后，递归调用reverseList函数，传入的参数是head->next，即当前头结点的下一个节点。这样就可以将问题转化为反转以head->next为头结点的子链表。

接下来，将head->next->next指向当前头结点head，实现链表节点的反转。

最后，将head->next指向nullptr，将原来的头结点变为尾节点。

最后，返回递归调用的结果newHead，即反转后的链表的头结点。

整个递归过程会一直向下递归到链表的最后一个节点，然后从最后一个节点开始逐个返回，直到返回整个反转后的链表的头结点。