欣迪

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?

思路

剛開始對 Linked list 不熟,很容易把問題想得很複雜。後來拿紙筆出來畫一畫之後,想法清楚很多。 Linked list 真的是超需要拿紙筆出來想的題目啊。

先上解法,再來說明

var reverseList = function(head) {
    if (!head) return head
    let prev = null
    let current = null
    let node = head
    while(node !== null) {
        current = new ListNode(node.val, prev)
        prev = current
        node = node.next
    }
    return current
};

首先,我們其實不需要去真的更動原本給的 node 的值,我們只要能再最後給一個對的 node 串的 head 就可以。

所以其實是要把想辦法把箭頭反過來。原本的起始值 1 直接連到 null , 當最後一個,然後倒著從後面加回去。

一邊用原始的 Linked list 往下找,一邊複製 node 的值然後指到前一個被複製的 node

等到全部跑完之後,最後的做出來的 node ,就是反轉過來的 Node list 的 head.

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。