【leetcode100-023】【链表】反转链表

【题干】

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

【思路】

太经典了，感觉也没什么必要用文字来描述了，今天实在太累了，直接代码吧。

【题解】

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 申请节点，pre和 cur，pre指向null
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            // 记录当前节点的下一个节点
            ListNode* tmp = cur->next;
            cur->next = pre;
            // pre和cur节点都前进一位
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        // 这里的cur就是最后一个节点
        ListNode* cur = reverseList(head->next);
		// 这里请配合动画演示理解
		// 如果链表是 1->2->3->4->5，那么此时的cur就是5
		// 而head是4，head的下一个是5，下下一个是空
		// 所以head.next.next 就是5->4
        head->next->next = head;
        // 防止链表循环，需要将head.next设置为空
        head->next = nullptr;
        // 每层递归函数都返回cur，也就是最后一个节点
        return cur;
    }
};