#include <iostream>
#include <vector>
#include<algorithm> 
using namespace std;
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 *cur ;
        ListNode* temp1, * temp2 ;
        if(head == nullptr || head->next == nullptr) return head;//处理链表为空或者长度为1
        if(head->next->next == nullptr)//处理链表长度为2
        {
            temp1 = head;
            temp2 = head->next;
            temp2->next = temp1;
            temp1->next = nullptr;
            return temp2;
        }
    //处理链表长度为3及其以上
        temp1 = head;
        cur = temp1->next;
        temp2 = cur->next;
        while (temp2 != nullptr)
        {
            cur->next = temp1;
            if (temp1 == head)
            {
                temp1->next = nullptr;
                temp1 = cur;
            }     
            else temp1 = cur;
            cur = temp2;
            if(cur->next != nullptr) temp2 = cur->next;//检查链表是否到底
            else
            {
                cur->next = temp1;
                break;
            }
        }
        return cur;
    }
};
int main()
{
    vector<int> head = { 1,2,3,4,5,6 };
    ListNode* head_test = new ListNode(0);
    ListNode* test  , *cur = head_test;
    Solution  a;
    for (int i = 0; i < head.size(); i++)
    {
       ListNode* temp = new ListNode(head[i]);
       cur->next = temp;
       cur = cur->next;
    }
    cur->next = nullptr;
    cur = head_test;
    cout << "cur list" << endl;
    while (cur->next != nullptr)
    {
        cout << cur->val << ' ';
        cur = cur->next;
    }
    cout << cur->val << endl;
    test = a.reverseList(head_test->next);
    while (test->next != nullptr)
    {
        cout << test->val << ' ';
        test = test->next;
    }
    cout << test->val << ' ';
  return 0;
}

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur ;
        ListNode* temp1, * temp2 ;
        cur = head;
        temp1 = nullptr;
        while (cur)
        {
            temp2 = cur->next;
            cur->next = temp1;
            temp1 = cur;
            cur = temp2;
        }
        return temp1;
    }
};

class Solution {
public:
    ListNode* reverse(ListNode *pre , ListNode * cur) {
        if (cur == nullptr)return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        return reverse(cur , temp);
    }
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr , 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) {
        if(head == nullptr) return head;
        ListNode *pre = nullptr;
        ListNode *cur = head;
        ListNode *cur_next = cur->next;
        while(cur != nullptr)
        {
            cur_next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = cur_next;
        }
        return pre;
    }
};