反转链表Ⅰ

头插法

/**
 * 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) {
        ListNode* new_head = nullptr;

        while(head) {
            ListNode* tmp = head;
            head = head->next;
            tmp->next = new_head;
            new_head = tmp;
        }

        return new_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) {
        ListNode* cur = head;
        ListNode* pre = nullptr;

        while(cur) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }

        return pre;
    }
};

递归法

/**
 * 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 || !head->next) {return head;}

        ListNode* new_head = reverseList(head->next);

        head->next->next = head;
        head->next = nullptr;

        return new_head;
    }
};

递归法解析：
1.new_head是固定的，就是原始链表的最后一个结点，作为反转后链表的头节点
2.最重要的一步 head->next->next = head; 其实可以把head->next看作当前结点的下一个节点(原始链表的顺序)，然后把当前节点的下一个节点的next指向当前节点，就实现了反转
3.把当前节点的next指向null
4.相较于原地逆置链表中有tmp结点来记住后面的节点，递归通过将节点信息保存在栈中来记住前一个节点