Logic, Linked Lists
Imagine we have a singly-linked linked list:
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:
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.
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."""