Linked List Print Reverse

  Let's solve a question from LeetCode called "Print Reverse of a Linked List" using the concept of printing a linked list in reverse order.

Problem Statement: Given the head of a linked list, print the elements of the list in reverse order.

Example: Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 5 4 3 2 1

To solve this problem, we can use a recursive approach. We'll define a recursive function that takes the head of the linked list as input and recursively prints the elements in reverse order. We'll traverse the list recursively until we reach the end, and then print the elements in reverse order during the backtracking.

Here's the complete code to solve the problem:


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def print_reverse(head):
    # Base case: if the current node is None, return
    if head is None:
        return

    # Recursive call to print the next node in reverse order
    print_reverse(head.next)

    # Print the value of the current node
    print(head.val, end=' ')


# Example usage
# Create a linked list with nodes [1, 2, 3, 4, 5]
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# Print the linked list in reverse order
print_reverse(head)

In this code, we create a linked list with nodes [1, 2, 3, 4, 5]. We then call the print_reverse function, passing the head of the linked list as input. The function recursively traverses the list until it reaches the end, and then prints the values in reverse order during the backtracking. The output is "5 4 3 2 1".

Time and Space Complexity Analysis: The time complexity of this solution is O(N), where N is the number of nodes in the linked list. We recursively traverse the list once, visiting each node exactly once.

The space complexity is O(N), where N is the number of nodes in the linked list. This is because the recursive calls use the call stack to store the function calls, and the maximum depth of the call stack is equal to the number of nodes in the list.

 

 

Next Post Previous Post