Reverse Linked List

Clarify the problem:

• The problem requires reversing a singly linked list.
• We need to implement a function that takes the head of a linked list as input and returns the new head of the reversed list.

Analyze the problem:

• Input: The head node of a linked list.
• Output: The head node of the reversed linked list.
• Constraints:
  • The linked list may be empty.
  • We need to reverse the list in-place, without creating a new list.

Design an algorithm:

• We can solve this problem using the iterative approach.
• We need to keep track of three pointers: prev, curr, and next.
• Initialize prev as None and curr as the head of the linked list.
• While curr is not None:
  • Store the next node of curr in the next pointer.
  • Set the next pointer of curr to prev, reversing the link.
  • Move prev to curr and curr to next for the next iteration.
• Finally, set the head of the reversed list as prev and return it.

Explain your approach:

• We will implement a function called reverseList that takes the head of a linked list as input.
• We initialize three variables: prev as None, curr as the head, and next as None.
• We enter a while loop that continues until curr is not None.
• Inside the loop, we assign next as the next node of curr.
• We reverse the link by setting the next pointer of curr to prev.
• We move prev to curr and curr to next.
• After the loop ends, we set the head of the reversed list as prev and return it.

Write clean and readable code:

python

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

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    return prev

Test your code:

python

# Test case 1
# Input: 1 -> 2 -> 3 -> 4 -> 5 -> None
# Reversed list: 5 -> 4 -> 3 -> 2 -> 1 -> None
# Expected output: 5 -> 4 -> 3 -> 2 -> 1 -> None
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)
reversed_head = reverseList(head)
while reversed_head:
    print(reversed_head.val, end=" -> ")
    reversed_head = reversed_head.next
print("None")

# Test case 2
# Input: 1 -> None
# Reversed list: 1 -> None
# Expected output: 1 -> None
head = ListNode(1)
reversed_head = reverseList(head)
while reversed_head:
    print(reversed_head.val, end=" -> ")
    reversed_head = reversed_head.next
print("None")

The chosen test cases include:

• A linked list with multiple nodes.
• A linked list with a single node.

Optimize if necessary:

• The iterative approach has a time complexity of O(n), where n is the number of nodes in the linked list. We need to traverse the entire list once.
• The space complexity is O(1) since we only use a constant amount of extra space for the prev, curr, and next pointers.

Handle error cases:

• We need to consider the case where the input linked list is empty (head is None). In this case, we can simply return None as the reversed list.

Discuss complexity analysis:

• Let n be the number of nodes in the linked list.
• The time complexity of the solution is O(n) since we need to traverse the entire list once.
• The space complexity is O(1) since we use a constant amount of extra space for the pointers.