Hackbright Code Challenges

Pivot Linked List: Solution

Pivot Linked List: Solution

Problem

Pivot Linked List

Whiteboard

Harder

Challenge

Medium

Concepts

Logic, Linked Lists

Download

pivot-ll-solution.zip


The solution is to make two new linked lists (called a and b in the solution code). You can then walk the original linked list and add items before the pivot to a and items after the pivot to b. The method can then return a new list combining both a and b.

pivot.py
class LinkedList(object): # ...
    def pivot(self, pivot):
        """Pivot list around value."""

        # START SOLUTION

        # a, b will be two next lists of before-pivot and
        # equal-or-after-pivot
        a = LinkedList()
        b = LinkedList()

        curr = self.head

        # Walk through current list, adding each item to either a or b

        while curr:

            # Note which item follows this in original list
            follow = curr.next
            curr.next = None

            # Add to proper list

            if curr.data < pivot:
                a.add_node(curr)
            else:
                b.add_node(curr)

            # Go to next item in original list
            curr = follow

        # Fix so b follows a and the tail of b is always the end
        a.tail.next = b.head
        b.tail.next = None

        # Fix this list to use a and b
        self.head = a.head
        self.tail = b.tail