0206. Reverse Linked List

Easy | Linked List + Two Pointer | 16 ms (98.94%), 15.4 MB (80.06%)

Source: LeetCode - Reverse Linked List GitHub: Solution / Performance

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

Constraints:

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

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

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

Input: head = []
Output: []

We need two pointers, one for recording the previous node, and the other one for iterating the linked list.

We reverse the linked list by modifying the current node's next pointer to make it point to the previous node.

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # (base case)
        if not head: return head
        if not head.next: return head
        
        # ==================================================
        #  Linked List                       (Iterative)   =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        prev = None
        
        while head:
            # STORE next node for next iteration
            tmp = head.next
            
            # RE-ASSIGN next pointer to prev node
            head.next = prev
            
            # ASSIGN prev node to current node
            prev = head
            
            # MOVE current node to next node
            head = tmp
        
        return prev

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # (base case)
        if not head: return head
        if not head.next: return head
        
        # ==================================================
        #  Linked List                       (Recursive)   =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        #                                             5-4-n
        # 1-2-3-4(head)-5(node)  ➜  1-2-3-4=5  ➜  1-2-3-4-n
        #
        #     5(node)-4-n             5-4-3       5-4-3-n
        # 1-2-3(head)-4-n        ➜  1-2-3=4    ➜  1-2-3-n
        
        node = self.reverseList(head.next)
        
        # recursion will stop at the last element since head.next == None
        head.next.next = head
        head.next = None
        
        return node

class Solution {
    /**
     * @time  : O(n)
     * @space : O(1)
     */
    
    public ListNode reverseList(ListNode head) {
        if( head == null || head.next == null ) return head;
        
        ListNode prev = null;
        while( head != null ){
            ListNode tmp = head.next;
            head.next = prev;
            prev = head;
            head = tmp;
        }
        return prev;
    }
}

Previous0023. Merge k Sorted Lists Next0019. Remove Nth Node From End of List

Last updated 4 years ago