# 【LeetCode】145. Reverse Linked List

## Question link
[Link](https://leetcode.com/problems/reverse-linked-list/)

## Intuition
> Given the `head` of a singly linked list, reverse the list, and return _the reversed list_.
(給定串列鏈結，將其翻轉並將其回傳)

題目要求需要翻轉整個串列鏈結，首先需要了解翻轉一個節點所需要的資訊是
1. 當前節點`curr`
2. 上個節點`prev`
3. 下個節點`next`
1. 記住下個節點的資訊
2. 將當前節點指向上一個節點
3. 更新下個節點
4. 更新當前節點

## Approach
1. 宣告 `prev = NULL`，用於指向個節點，而對於開頭節點來說上個節點為空所以初始化為NULL
2. 宣告 `curr`，用於指向當前節點
3. 循環整個串列鏈節直到`curr`為空
1. 使用`temp`，將下個節點記錄起來
2. 將當前節點指向上一個節點`curr->next = prev`
3. 更新上個節點 `prev = curr`
4. 更新當前節點 `curr = temp`
4. 回傳上個節點，由於迴圈的條件是當前節點為空

## Complexity

- Time complexity: $O(n)$
- Space complexity: $O(1)$

## Code

### Solution 1

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while(curr) {
        struct ListNode* temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = temp;
    }
    return prev;
}