This Leetcode question asks about how to reverse a linked list. I was thinking that this would be cool to solve with a song! What if we represent a song as a linked list and then reverse it? Then, we could hear the song backwards!

In order to reverse a linked list, we need to keep track of three things:

1. previous node (we will start it as None; because there is no node before the head)

2. current node (we will start it as head; the first node in the list)

3. next node (to save the reference before we change pointers)

Thanks for reading Learning Data Structures and Algorithms with Music! Subscribe for free to receive new posts and support my work.

In order to reverse the list, first, we need to save a reference to the next node before we change any pointers.

tmp = current.next

Next, we need to point the current node to the previous node. This is reversing the list - the next “arrows” are now pointing in the opposite direction. In order to do this, we would set

current.next = previous

Lastly, we need to move our pointers forward for the next iteration. We need to update both previous and current.

previous = current 
current = tmp

So the full reverseList() function becomes:

def reverseList(head): 
    previous = None 
    current = head 
    while current is not None: 
        tmp = current.next 
        current.next = previous 
        previous = current 
        current = tmp
    return previous

Now that we have our reverseList() function, we can try to experiment with music. In order to manipulate sound, we will use MIDI notes and create classes in Python that represent MIDI notes. This class represents a single MIDI note using note number, note velocity, the time in ticks, the MIDI channel, and critically, it needs the next pointer so that we can create a linked list from these notes.

from mido import MidiFile, MidiTrack, Message, MetaMessage
import os
import time

class NoteNode:
    “”“Node representing a single MIDI note”“”
    def __init__(self, event_type, note=None, velocity=None, time=None, channel=0, tempo=None, next=None):
        self.event_type = event_type
        self.note = note           # MIDI note number (0-127)
        self.velocity = velocity   # Note velocity (0-127)
        self.time = time          # Cumulative time in ticks
        self.channel = channel    # MIDI channel
        self.tempo = tempo
        self.next = None          # Pointer to next note
    
    def __str__(self):
        if self.event_type == ‘note_on’:
            return f”NoteOn(note={self.note}, vel={self.velocity}, time={self.time})”
        elif self.event_type == ‘note_off’:
            return f”NoteOff(note={self.note}, vel={self.velocity}, time={self.time})”
        elif self.event_type == ‘set_tempo’:
            return f”Tempo(tempo={self.tempo}, time={self.time})”
        else:
            return f”{self.event_type}(time={self.time})”

We will also create a class to construct a linked list, as in the last post, but this class will handle MIDI representation. This class appends the notes as a linked list using the next pointer, traverses and prints the notes in the list, and has our reverseList() function, and then saves the linked list as a MIDI file. The code needed to take special care with the reversal of notes by reversing note_off and note_on, and reversing the timing.

class MIDINoteLinkedList:
    “”“Linked list of MIDI notes extracted from a .mid file”“”
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def append(self, event_type, note=None, velocity=None, time=None, channel=0, tempo=None, next=None):
        “”“Add a note to the end of the list”“”
        new_node = NoteNode(event_type, note, velocity, time, channel, tempo, next)
        self.size += 1
        
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return
        
        self.tail.next = new_node
        self.tail = new_node
    
    def traverse(self, limit=None):
        “”“Print all notes in the list”“”
        if not self.head:
            print(”List is empty”)
            return
        
        current = self.head
        position = 0
        
        print(f”\nMIDI Note Linked List (Total notes: {self.size})”)
        print(”-” * 70)
        
        while current and (limit is None or position < limit):
            print(f”{position:4d}: {current}”)
            current = current.next
            position += 1
        
        if limit and self.size > limit:
            print(f”... and {self.size - limit} more notes”)
    
    def reverseList(self):
        “”“Reverse the linked list IN PLACE”“”
        prev = None
        current = self.head
        self.tail = self.head
        
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        
        self.head = prev
    
    def save_to_midi(self, output_path, ticks_per_beat=480, reverse_timing=False):
        “”“Convert the linked list back to a MIDI file
        
        Args:
            output_path: Where to save the MIDI file
            ticks_per_beat: MIDI timing resolution
            reverse_timing: If True, reverse the timing AND swap note_on/note_off
        “”“
        midi = MidiFile(ticks_per_beat=ticks_per_beat)
        track = MidiTrack()
        midi.tracks.append(track)
        
        # Add tempo
        track.append(MetaMessage(’set_tempo’, tempo=500000, time=0))
        
        # Collect events in LINKED LIST ORDER
        events = []
        current = self.head
        
        while current:
            if (current.event_type == ‘note_on’ or current.event_type == ‘note_off’) and current.note is not None:
                event_type = current.event_type
                
                # CRITICAL: When reversing, swap note_on and note_off
                # This ensures notes turn ON before they turn OFF
                if reverse_timing:
                    if event_type == ‘note_on’:
                        event_type = ‘note_off’
                    elif event_type == ‘note_off’:
                        event_type = ‘note_on’
                
                events.append({
                    ‘type’: event_type,
                    ‘note’: current.note,
                    ‘velocity’: current.velocity,
                    ‘time’: current.time,
                    ‘channel’: current.channel
                })
            current = current.next
        
        # Handle timing based on reverse_timing flag
        if reverse_timing and events:
            # Reverse the timing: last event becomes first
            max_time = max(e[’time’] for e in events)
            for event in events:
                event[’time’] = max_time - event[’time’]
        
        # Sort by time to get proper playback order
        events.sort(key=lambda x: x[’time’])
        
        # Write events with delta times
        prev_time = 0
        for event in events:
            delta_time = event[’time’] - prev_time
            
            if event[’type’] == ‘note_on’:
                track.append(Message(’note_on’, 
                                   note=event[’note’], 
                                   velocity=event[’velocity’], 
                                   time=delta_time,
                                   channel=event[’channel’]))
            else:  # note_off
                track.append(Message(’note_off’, 
                                   note=event[’note’], 
                                   velocity=event[’velocity’] if event[’velocity’] else 0, 
                                   time=delta_time,
                                   channel=event[’channel’]))
            
            prev_time = event[’time’]
        
        # Add end of track
        track.append(MetaMessage(’end_of_track’, time=0))
        
        midi.save(output_path)
        print(f”Saved to: {output_path}”)

Sweet! So these are the main pieces that we need to create a linked list out of a song and then reverse the linked list. Check out the next post to see how this sounds!