206 - Reverse Linked List

解法一 - In-place reversal

要 reverse linked list,就是要一次反轉一個 node。每次要反轉 current node 之前,都需要做幾步:

  1. 準備好反轉完 current node 要指向的 node(就是 prev)

每次迴圈都做:

  1. 先記錄 current node 的 next
  2. 把 current node 的 next 更新
  3. 準備好反轉完 current node 要指向的 node(就是 prev)
  4. 更新 current node 為 next
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr or head->next == nullptr) {
            return head;
        }

        ListNode *prev = nullptr, *next;

        while(head != nullptr) {
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }

        return prev;
    }
};

results matching ""

    No results matching ""