206.Reverse Linked List

Tags: [list], [linked_list], [reverse], [recursion], [iteration]

Com: {fb}

Link: https://leetcode.com/problems/reverse-linked-list/#/description

Reverse a singly linked list.

click to show more hints.

Hint:

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

Solution: Iteration

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head

        prev = None
        curr = head

        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next

        return prev

Revelation:

• See the below picture:

Note:

• Time complexity = O(n), n is the number of nodes of the given linked list.
• Space complexity = O(1).

Solution: Recursion

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # base case
        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

Revelation:

• head.next = None is for cutting the original link.

Note:

• Time complexity = O(n), n is the number of nodes of the given linked list.
• Space complexity = O(n), n is the number of nodes of the given linked list.