剑指offer：反转链表

原题链接https://www.acwing.com/problem/content/description/33/

参考链接：https://www.acwing.com/solution/content/6583/ （有动画）
y总：https://www.acwing.com/solution/content/743/

一个pre指针，保留前继节点，一个cur，指向当前节点，一个next，指向下一个节点。

每次：
next保存cur的下一个节点
cur的next指向pre
向后移动一位：pre移到cur，cur移动next

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
        // 记录前驱节点
        ListNode* pre = nullptr;
        auto cur = head;
        while(cur)
        {
    
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
};

递归：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    ListNode* reverseList(ListNode* head) {
    
        if(head == NULL) return NULL;
        if(head->next == NULL) return head;
        
        ListNode* p = head;
		
		// 先找到最后一个节点
        while(p->next->next != NULL)
        {
    
            p = p->next;
        }
        
        // 新建一个
        ListNode* new_head = p->next;
        p->next = NULL;
        ListNode* p2 = new_head;
        
        while(1)
        {
    
            p = head;
            
            if(p->next == NULL)
            {
    
                p2->next = p;
                break;
            }
            
            while(p->next->next)
            {
    
                p = p->next;
            }
            
            p2->next = p->next;
            p->next = NULL;
            p2 = p2->next;
        }
        
        return new_head;
    }
};