206. Reverse Linked List

[ZhongKuo0228]

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

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

The number of nodes in the list is the range [0, 5000]. -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

[ZhongKuo0228]

用python解：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        #將每個node的next改成prev，逐步改到最後一個node
        #先記住list每次的頭
        curr = head
        #prev的最開始是空值None
        prev = None

        while curr:
            #先用一個變數來儲存下一個node的資料
            next_node = curr.next
            #將next指向prev
            curr.next = prev
            #將prev指向原本的node
            prev = curr
            #最後將node值指回一開始暫存的變數node
            curr = next_node

        return prev

[ZhongKuo0228]

用js解

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {

    //需要三個變數，前一個節點prev，現在的節點current，下一個節點next
    let prev = null;
    let current = head;

    while (current !== null) {
        let next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    return prev;

};

[fockspaces]

recursion的寫法，其實 iterative (while) 比較節省記憶體，因為不需要存每個階段的 function 進 call stack，只要直接對 prev, head, next 指標操作即可

# Definition for asingly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode], prev = None) -> Optional[ListNode]:
        if head is None:
            return prev
        next = head.next
        head.next = prev
        prev = head
        return self.reverseList(next, prev)

[fockspaces]

GPT 解答，實在就是太高端

1. 邊界條件 -> 遇到 tail, return tail
2. head.next 直接指到 newHead 的最尾端，將其 .next 指向自己
3. 回傳 newHead

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

[fockspaces]

又忘記這個方法，prev = None

1. prev = None，prev 代表反轉 nodes 的頭
2. 紀錄 next_node，並把 prev 變為當前 head 為首的 reverse nodes
3. 每次往後傳遞，直到沒有 head 時 回傳 prev（代表已經是以 5 為首的 nodes）

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode], prev = None) -> Optional[ListNode]:
        if not head:
            return prev
        next_node = head.next
        head.next = prev
        prev = head
        return self.reverseList(next_node, prev)