Given the head of a singly linked list, reverse the list, and return the reversed list.

給一個 linked list 將他反轉。

Example

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

Coding

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let prev = null;
    while (head) {
        next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev; 
};

創建一個 prev 指向 null

移動 next 到 head 的下一個 node

將 head 的 next 連接到 prev

移動 prev 到 head （初始化 prev 指針）

移動 head 到 next （移動到下一個要處理的 node）

移動 next 到下一個 node

將 head 的 next 連接到 prev

移動 prev 到 head （初始化 prev 指針）

移動 head 到 next （移動到下一個要處理的 node）

以此類推到 head 移動到 null。

Time complexity: O(n)