Shuffle Playlist - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-35 mins
  • 🛠️ Topics: Linked Lists, Reordering, Pointer Manipulation

1: U-nderstand

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

  • Q: What does the problem ask for?
    • A: The problem asks to reorder a singly linked list so that it alternates between the first and last elements in the original list.
  • Q: What should be returned?
    • A: The function should return the head of the shuffled list.
HAPPY CASE
Input: 
    - playlist1 = Node(1, Node(2, Node(3, Node(4))))
    - playlist2 = Node(('Respect', 'Aretha Franklin'),
                        Node(('Superstition', 'Stevie Wonder'),
                            Node(('Wonderwall', 'Oasis'),
                                Node(('Like a Prayer', 'Madonna'),
                                    Node(('Bohemian Rhapsody', 'Queen'))))))
Output: 
    - 1 -> 4 -> 2 -> 3
    - ('Respect', 'Aretha Franklin') -> ('Bohemian Rhapsody', 'Queen') -> ('Superstition', 'Stevie Wonder') -> ('Like a Prayer', 'Madonna') -> ('Wonderwall', 'Oasis')
Explanation: 
    - The list is reordered to alternate between elements from the start and end of the original list.

EDGE CASE
Input: 
    - playlist = Node(1, Node(2))
Output: 
    - 1 -> 2
Explanation: 
    - The list has only two elements, so no reordering is necessary.

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 involving Reordering and Merging, we want to consider the following approaches:

  • Finding the Middle: Use a slow and fast pointer to find the middle of the list.
  • Reversing a Sublist: Reverse the second half of the list.
  • Merging: Merge the two halves alternately.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will split the linked list into two halves, reverse the second half, and then merge the two halves by alternating nodes from each half.

1) Initialize two pointers `slow` and `fast` to find the middle of the list.
2) Reverse the second half of the list.
3) Merge the two halves by alternating nodes from each half.
4) Return the head of the newly reordered list.

⚠️ Common Mistakes

  • Forgetting to correctly handle lists with odd or even lengths.
  • Incorrectly managing pointers, leading to loss of nodes or 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

def shuffle_playlist(playlist):
    if not playlist or not playlist.next:
        return playlist
    
    # Step 1: Find the middle of the list
    slow, fast = playlist, playlist
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Step 2: Reverse the second half
    prev, curr = None, slow.next
    slow.next = None  # Split the list into two halves
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    
    # Step 3: Merge the two halves
    first, second = playlist, prev
    while second:
        next_first, next_second = first.next, second.next
        first.next = second
        second.next = next_first
        first = next_first
        second = next_second
    
    return playlist

5: R-eview

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

  • Example: Use the provided playlist1 and playlist2 linked lists to verify that the function correctly shuffles the playlists.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the length of the playlist.

  • Time Complexity: O(N) because we traverse the entire list multiple times (finding the middle, reversing, and merging).
  • Space Complexity: O(1) because the algorithm uses a constant amount of extra space for pointers.