链表#简单#反转链表

前文

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

示例 2：

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

示例 3：

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

正文

/**
 * 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) {

    }
};

解法1

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

创建一个标识为前一个的prev和标识为当前的curr指针，curr指针最开始当前为head， 如果当前指针不是空指针，循环当前指针，循环过程为： 找到当前指针的下一个并存储为next，将prev指针赋给当前指针的下一个， 此时因为刚刚已经用next存储了当前指针的下一个，所以下一个指针还在， 此时将当前指针赋给prev，然后将next赋给当前指针curr。

过程演示：

// 设链表为：

1->2->3->4->nullptr

// 其中格式意思是 x, 0xaddress，前一个是值，后一个0x表示值为x的地址

开始时 head = 1->2->3->4->nullptr

进入函数：
prev = nullptr
curr = head = 0x1
循环：
	// 下方为开始时
	next = curr->next // 即 next = 2->3->4->null
	curr->next = prev // 即 1->next = null
	prev = curr // 即 prev = 1->null
	curr = next // 即 curr = 2->3->4->nullptr
	// 进入下一个循环：
	// next = 3->4->null
	// 2->next = 1->null
	// prev = 2->1->null
	// curr = 3->4->nullptr
	// ... 依次类推

解法2 递归

本质上，反转链表需要将后一个元素指向之前的元素，即每次第一个元素指向之前的元素。 同时存储之前元素，因此递归也可以很好解决：

ListNode* reverse1(ListNode *prev, ListNode *curr) {
  if (curr == nullptr)
    return prev;
  
  ListNode* next = curr->next;
  curr->next = prev;
  prev = curr
  return reverse1(prev, next);
}

reverse1(nullptr, head);

递归中，每次将当前元素的下一个指向之前元素，同时递归下一个元素。

递归第一次：
1->nullptr，递归（1->nullptr, 2->3->4->nullptr）
递归第二次：
2->1->nullptr，递归（2->1->nullptr, 3->4->nullptr）
依次直到递归至nullptr，即反转完成