206. 反转链表

给你单链表的头节点 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
 

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-linked-list
著作权

归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<iostream>
using namespace std;
class ListNode
{
public:ListNode* next;int data;ListNode(){next = NULL;}
};
class LinkList
{
public:int len;ListNode* head;LinkList(){head = new ListNode();head->next = NULL;len = 0;}void insert(int index, int num){if (index > len || index < 0){return;}//找到前一位的index前一位else{ListNode* p = head;for (int i = 0; i < index; i++){p = p->next;}ListNode* node = new ListNode();node->data = num;node->next = p->next;p->next = node;len++;}}void del(int index){if (index >= len || index < 0){return;}else{ListNode* node = new ListNode;ListNode* p = head;for (int i = 0; i < index; i++){p = p->next;}//要删除的前一个位置ListNode* q = p->next;p->next = p->next->next;delete q;len--;}}LinkList* reverseList(){//方法1//把每次ListNode* p = head;LinkList* newone = new LinkList();ListNode* q = ( * newone).head;for (int i = 0; i < len; i++){p = p->next;newone->insert(0, p->data);//每次都插入到首位置中去}return newone;}//方法2ListNode* reverselist(ListNode* head){if (head == NULL || head->next == NULL)return head;ListNode* tail = head->next;//先记录反转后的尾结点ListNode* new_head = reverselist(head->next);head->next = tail->next;tail->next = head;return new_head;}void display(){ListNode* p = head->next;for (int i = 0; i < len; i++){if (i) {cout << p->data;}else{cout << "," << p->data;}p = p->next;}}
};
int main()
{int n;LinkList l1;cin >> n;for (int i = 1; i <= n; i++){cout << i;l1.insert(i - 1, i);}l1.display();cout << endl;l1.reverseList()->display();return 0;
}