Two Pointer Reverse List - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Two-pointer technique

Unit 1 Session 2 (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the function?

  • A: The input is a list lst containing elements that need to be reversed.

• Q: What is the expected output of the function?

  • A: The function should return the same list with its elements reversed.

• Q: Should the reversal be done in-place?

  • A: Yes, the reversal should be done in-place, meaning the original list should be modified without using extra space for another list.

• Q: Can the list contain any data types?

  • A: The problem assumes the list contains elements that can be swapped, typically integers or strings.

• Q: What should the function return if the list is empty?

  • A: If the list is empty, the function should return the empty list.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use the two-pointer approach to reverse the list in-place. One pointer starts at the beginning (left) and the other starts at the end (right). Swap the elements at these pointers and then move the pointers towards each other until they meet.

1) Initialize two pointers: `left` at the start of the list and `right` at the end of the list.
2) While `left` is less than `right`:
   - Swap the elements at `lst[left]` and `lst[right]`.
   - Move the `left` pointer one step to the right.
   - Move the `right` pointer one step to the left.
3) Return the modified list after all elements have been swapped.

⚠️ Common Mistakes

• Forgetting to move the pointers after swapping, which can lead to an infinite loop.
• Incorrectly swapping elements, leading to an incorrect reversal.
• Assuming the list is not modified in-place when it should be.

I-mplement

def reverse_list(lst):
    left = 0
    right = len(lst) - 1
    
    while left < right:
        # Swap elements at left and right pointers
        lst[left], lst[right] = lst[right], lst[left]
        
        # Move pointers towards each other
        left += 1
        right -= 1
    
    return lst