206.反转链表

一、双指针

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp；
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur)
        {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

二、递归

将整个链表看成两个结点，第一个是头结点，第二个是待翻转的部分（递归调用），每次将头结点的下一个点指向头结点，并将头结点的next指针指向NULL

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 边缘条件判断
        if(head == NULL) return NULL;
        if (head->next == NULL) return head;
        // 递归调用，翻转第二个节点开始往后的链表
        ListNode *last = reverseList(head->next);
        // 翻转头节点与第二个节点的指向
        head->next->next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head->next = NULL;
        return last;
    }
};