# 206. Reverse Linked List

> ***View the book with <i class="fa fa-book"></i> Book Mode.***

- [**LeetCode筆記目錄**](https://hackmd.io/@WeiYee/SyABdj_eA)

## :book: 題目

**網址:** https://leetcode.com/problems/reverse-linked-list/description/

## :dart: 解題步驟
- 用遞迴，需要一個 ListNode 紀錄目前整理的。
- 當 head 為 null 則返回 ListNode (**整理**)
- 每次新增一個 ListNode (**暫時**)，值和當前 head 一樣，但指向 ListNode (**整理**)
- 然後遞迴
- 舉例

  Head: 4 -> 5 -> 6 
  整理: 3 -> 2 -> 1 
  暫時: 4 -> 整理 

## :pencil2: 程式碼
### C++ (迴圈)

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

    }
};

### Java (遞迴)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        return process(head, null);
    }

    private ListNode process(ListNode head, ListNode ans) {
        if (head == null) return ans;
        ListNode temp = new ListNode(head.val);
        temp.next = ans;
        ans = temp;
        return process(head.next, ans);
    }
}