Move Tail to Front of Linked List - codepath/compsci_guides GitHub Wiki

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

TIP102 Unit 5 Session 2 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10-15 mins
  • 🛠️ Topics: Linked Lists, Manipulation

1: U-nderstand

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

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What happens if the linked list is empty?
    • If the linked list is empty, the function should return None.
  • What happens if there is only one node in the linked list?
    • If there is only one node, the list remains unchanged.
HAPPY CASE
Input: head = Node("Daisy") -> Node("Mario") -> Node("Toad") -> Node("Peach")
Output: Node("Peach") -> Node("Daisy") -> Node("Mario") -> Node("Toad")
Explanation: The tail of the linked list "Peach" is moved to the front.

EDGE CASE
Input: head = Node("Daisy")
Output: Node("Daisy")
Explanation: When the linked list has only one node, it remains unchanged.

EDGE CASE
Input: head = None
Output: None
Explanation: When the linked list is empty, the function returns None.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Linked List problems, we want to consider the following approaches:

  • Traversal of a linked list
  • Modification of pointers to move nodes

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the linked list to find the last node and move it to the front.

1) If the head is `None` or there is only one node, return the head.
2) Initialize two pointers: `prev` as `None` and `current` as `head`.
3) Traverse the linked list to find the second-to-last and last nodes.
4) Set the `next` of the second-to-last node to `None` (removing the last node).
5) Set the `next` of the last node to the current head.
6) Update the head to be the last node.
7) Return the updated head.

⚠️ Common Mistakes

  • Forgetting to handle the case where the linked list is empty or has only one node.
  • Not correctly updating the pointers, leading to incorrect list structure.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

# For testing
def print_linked_list(head):
    current = head
    while current:
        print(current.value, end=" -> " if current.next else "\n")
        current = current.next

def tail_to_head(head):
    if head is None or head.next is None:
        return head
    
    prev = None
    current = head
    
    # Traverse the list to find the second-to-last and last nodes
    while current.next:
        prev = current
        current = current.next
    
    # Move the tail to the front
    if prev:
        prev.next = None
        current.next = head
        head = current
    
    return head

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through your code with an input to check for the expected output
  • Catch possible edge cases and off-by-one errors

Example:

head = Node("Daisy", Node("Mario", Node("Toad", Node("Peach"))))
# Linked List: Daisy -> Mario -> Toad -> Peach
print_linked_list(tail_to_head(head))
# Expected Output: Peach -> Daisy -> Mario -> Toad

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work. Assume N represents the number of nodes in the linked list.

  • Time Complexity: O(N) because we need to traverse the entire linked list to find the last node.
  • Space Complexity: O(1) because we are only modifying the pointers and not using extra space.