0206 Reverse Linked List

Solved at: 2023-01-28 Reverse Linked List

Question

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

Solution

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var itr: ListNode? = head
        guard itr != nil else { return nil }
        var prev : ListNode = itr!
        while (itr != nil) {
            var next : ListNode? = itr!.next
            itr!.next = prev
            prev = itr!
            itr = next
        }
    }
}

causes time limit exceeded

Improved

i was like -- what -- why?

then I figured it was because the last two elements, previously head, had an infinite loop. therefore, the printing answer part caused the error.

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var itr: ListNode? = head
        guard itr != nil else { return nil }
        var prev : ListNode? = nil // ← this
        while (itr != nil) {
            var next : ListNode? = itr!.next
            itr!.next = prev
            prev = itr
            itr = next
        }
        return prev
    }
}

Results

Runtime 12 ms, Beats 81.49%
Memory 15 MB, Beats 45.31%

Complexity Analysis

Time $O(n)$ Space $O(1)$

Other Answers Online

Recursive approach

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        guard head != nil else { return nil }
        guard head!.next != nil else { return head }
        var next : ListNode? = head!.next
        var reversed : ListNode? = reverseList(next);
        head!.next!.next = head
        head!.next = nil
        return reversed
    }
}

Runtime 12 ms, Beats 81.49%
Memory 14.6 MB, Beats 91.58%