Hackbright Code Challenges

Pivot Linked List

Pivot Linked List

Whiteboard

Harder

Challenge

Medium

Concepts

Logic, Linked Lists

Download

pivot-ll.zip

Solution

Pivot Linked List: Solution


Imagine we have a singly-linked linked list:

digraph test { rankdir=LR 7 -> 6 -> 2 -> 3 -> 9 -> a1 -> b1 a1 [label=1] b1 [label=1] }

In this challenge, you’ll be given a value and you want to rearrange the items in the linked list so that all items with data less than the given value are in the first half, and items with greater than or equal to the given value are in the second half.

For example, for the value 5:

digraph test2 { rankdir=LR 2 -> 3 -> b1 -> a1 -> 7 -> 6 -> 9 b1 [label=1] a1 [label=1] }

Notice that this list isn’t sorted; all we need to do is “pivot” it around the given value. Otherwise, items are still in the same order as they were (7 came before 6 in the original list, so it still does — but both of them are greater than 5, so they appear in the second half).

For example:

>>> ll = LinkedList([7, 6, 2, 3, 9, 1, 1])

>>> ll.pivot(5)

>>> ll.print_list()
2 3 1 1 7 6 9

If the given pivot value is in the list, it should appear in the second half (with other greater-than-or-equal-to values):

>>> ll = LinkedList([7, 6, 2, 5, 3, 5, 9, 1, 1])

>>> ll.pivot(5)

>>> ll.print_list()
2 3 1 1 7 6 5 5 9

We’ve provided a functioning LinkedList class an a stub for the pivot method. Implement this.

pivot.py
class LinkedList(object):
    """Singly-Linked list."""

    def __init__(self, values=None):
        """Set up list with optional starting data."""

        self.head = None
        self.tail = None

        if values:
            for value in values:
                self.add_data(value)

    def add_data(self, value):
        """Add node with given data.

            >>> ll = LinkedList()
            >>> ll.add_data(2)
            >>> ll.add_data(1)
            >>> ll.print_list()
            2 1 
        """

        node = Node(value)
        self.add_node(node)

    def add_node(self, node):
        """Add node.

            >>> ll = LinkedList()
            >>> ll.add_node(Node(2))
            >>> ll.add_node(Node(1))
            >>> ll.print_list()
            2 1 
            >>> ll.tail.data
            1
        """

        if self.head is None:
            self.head = node

        else:
            curr = self.head
            while curr.next:
                curr = curr.next

            curr.next = node

        self.tail = node

    def print_list(self):
        """Print list as space-separated data."""

        curr = self.head

        while curr:
            print(curr.data, end=' ')
            curr = curr.next

        print()

    def pivot(self, pivot):
        """Pivot list around value."""