【力扣 206】反转链表 C++题解（链表+头插法）

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

示例 1：

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

输入：head = [1,2]
输出：[2,1]
示例 3：

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

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

---

思路

首先，检查输入的链表是否为空，如果为空，则直接返回空。然后，创建一个新的链表头节点head2，并设置一个指针p2用于遍历新链表，另一个指针p1用于遍历原链表。

接着，进入一个循环，在循环中，每次都从原链表中取出一个节点，然后在新链表的头部插入这个节点。具体操作是先创建一个新的节点p2，复制原链表当前节点的值，然后将p2的next指向head2的next，即新链表的头部，然后再将head2的next指向p2，完成头部插入。最后，将p1向后移动一位，继续下一次循环。

当原链表遍历完毕后，循环结束。这时，新链表的头部还是空节点，所以需要将head2向后移动一位，跳过这个空节点。

最后，函数返回新链表的头部指针，即完成了链表的反转。

---

AC代码

/*
 * @lc app=leetcode.cn id=206 lang=cpp
 *
 * [206] 反转链表
 */

// @lc code=start
/**
 * 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) {
        if(head == nullptr) {
            return nullptr;
        }
		ListNode* head2 = new ListNode();
		ListNode* p2 = nullptr;
		ListNode* p1 = head;
		while (p1 != nullptr){
			p2 = new ListNode(p1->val);
			p2->next = head2->next;
			head2->next = p2;
			p1 = p1->next;
        }
		head2 = head2->next;
		return head2;
	}
};
// @lc code=end