# 【LeetCode】 206. Reverse Linked List

## Description
> Reverse a singly linked list.

> Follow up:
> A linked list can be reversed either iteratively or recursively. Could you implement both?

> 反轉一個單向的串列鏈結。

> 進階：
> 一個串列鏈結可以用迭代或是遞迴實作，你可以兩種都實作嗎？

## Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

## Solution

* 設三個點：前一個、現在、下一個。
* 每次Loop，把現在的`next`設為前一個，接著把三個點都往下移。重複至到尾巴(`NULL`)。
* 遞迴的比較想法困難，把點拆為兩個兩個一組，將後面的點的`next`往回設，將自己的點的`next`設為`NULL`。然後用遞迴從後面開始往回做。

### Code

* Iteratively

/**
 * 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* next = head->next;
        ListNode* newHead = head;
        ListNode* pre = NULL;
        
        while(next)
        {
            pre = newHead;
            newHead = next;
            next = newHead->next;
            newHead->next = pre;
        }
        head->next = NULL;
        return newHead;
    }
};

* Recursively

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

###### tags: `LeetCode` `C++`