【LeetCode】145. Reverse Linked List

Question link

Link

Intuition

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

題目要求需要翻轉整個串列鏈結，首先需要了解翻轉一個節點所需要的資訊是

1. 當前節點curr
2. 上個節點prev
3. 下個節點next
4. 記住下個節點的資訊
5. 將當前節點指向上一個節點
6. 更新下個節點
7. 更新當前節點

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;
}