Leetcode题目链接：206. 反转链表

题目描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

题目示例：

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例3:

输入：head = []
输出：[]

解题思路：

• 双指针

  • 定义前置指针pre，初始化为NULL，指向当前处理的元素的前一个位置

  • 定义当前指针current，初始化为head，指向当前正在处理的元素位置

  • 定义后置指针post，初始化为NULL，指向当前正在处理的元素的后一个位置（即将要处理的下一个元素的位置）

  • 当cur不为空，即当前链表中还存在处理的元素时继续执行循环

  • 更改指针指向

    • 记录后置指针的位置，防止反转当前位置元素的next指针后链表指向断裂，即post = current -> next

    • 反转当前元素的指针指向，使当前元素指向前置元素，即current -> next = pre

  • 指针后移

    • pre指针后移，即pre = current

    • current指针后移，即current = post

  • 当循环结束时，pre指向原先链表的最后一个元素位置（反转后的链表第一个元素位置），返回pre指针即可

• 递归

  • 定义reverse()函数，用于递归处理链表元素的反转

  • 在reverseList()函数中调用reverse()函数，并赋予调用的初始值（cur = head， pre = NULL）

  • 编写reverse()函数

    • 定义边界条件，即当cur == NULL时链表中所有元素均已反转完成，返回pre指针以退出最深层的函数调用，依次返回上一次的函数调用

    • 更改指针指向

      • 记录后置指针的位置，防止反转当前位置元素的next指针后链表指向断裂，即ListNode* post = cur -> next

      • 反转当前元素的指针指向，使当前元素指向前置元素，即cur -> next = pre

    • 进行多次递归调用，即reverse(post,cur)

我的答案：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

//双指针写法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = NULL,*current = head,*post = NULL;
        while(current != NULL){
            post = current -> next;
            current -> next = pre;
            pre = current;
            current = post;
        }
        return pre;
    }
};

//递归写法
class Solution {
public:
    ListNode* reverse(ListNode* cur, ListNode* pre) {
        if(cur == NULL) return pre;
        ListNode* post = cur -> next;
        cur -> next = pre;
        return reverse(post,cur);
    }

    ListNode* reverseList(ListNode* head) {
        return reverse(head,NULL);
    }
};

提交结果：

双指针写法

递归写法