02

力扣206翻转链表

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

---

1、直接翻转

/**
 * 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* temp;
        ListNode* pre=NULL;
        ListNode* cur=head;
        while(cur){
            temp=cur->next;
            cur->next=pre;
            pre=cur;  //没有next指向就是指向整个结构的前面
            cur=temp;
        }
        return pre;
    }
};

 2、递归翻转 递归链接：三道题套路解决递归问题 | lyl's blog (lyl0724.github.io)

（1）边界条件：if(head==NULL||head->next==NULL) return head;

（2）递归体：ListNode* last = reverseList(head->next);

（3）处理头指针的方法：head->next->next=head;   追加第一个指针

                                          head->next=NULL;   最后一个指针指向

/**
 * 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==NULL||head->next==NULL) return head;
        ListNode* last=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return last;
    }
};