<jupyter_start><jupyter_text>This notebook was prepared by [<NAME>](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).  Challenge Notebook  Problem: Partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.* [Constraints](Constraints)* [Test Cases](Test-Cases)* [Algorithm](Algorithm)* [Code](Code)* [Unit Test](Unit-Test)* [Solution Notebook](Solution-Notebook)  Constraints* Can we assume this is a non-circular, singly linked list?    * Yes* Do we expect the function to return a new list?    * Yes* Can we assume the input x is valid?    * Yes* Can we assume we already have a linked list class that can be used for this problem?    * Yes* Can we create additional data structures?    * Yes* Can we assume this fits in memory?    * Yes  Test Cases* Empty list -> []* One element list -> [element]* Left linked list is empty* Right linked list is empty* General case    * Partition = 10    * Input:  4, 3, 7, 8, 10, 1, 10, 12    * Output: 4, 3, 7, 8, 1, 10, 10, 12  AlgorithmRefer to the [Solution Notebook](http://nbviewer.ipython.org/github/donnemartin/interactive-coding-challenges/blob/master/linked_lists/partition/partition_solution.ipynb).  If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.  Code<jupyter_code># %load ../linked_list/linked_list.py
class Node(object):

    def __init__(self, data, next=None):
        self.next = next
        self.data = data

    def __str__(self):
        return self.data


class LinkedList(object):

    def __init__(self, head=None):
        self.head = head

    def __len__(self):
        curr = self.head
        counter = 0
        while curr is not None:
            counter += 1
            curr = curr.next
        return counter

    def insert_to_front(self, data):
        if data is None:
            return None
        node = Node(data, self.head)
        self.head = node
        return node

    def append(self, data):
        if data is None:
            return None
        node = Node(data)
        if self.head is None:
            self.head = node
            return node
        curr_node = self.head
        while curr_node.next is not None:
            curr_node = curr_node.next
        curr_node.next = node
        return node

    def find(self, data):
        if data is None:
            return None
        curr_node = self.head
        while curr_node is not None:
            if curr_node.data == data:
                return curr_node
            curr_node = curr_node.next
        return None

    def delete(self, data):
        if data is None:
            return
        if self.head is None:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        prev_node = self.head
        curr_node = self.head.next
        while curr_node is not None:
            if curr_node.data == data:
                prev_node.next = curr_node.next
                return
            prev_node = curr_node
            curr_node = curr_node.next

    def delete_alt(self, data):
        if data is None:
            return
        if self.head is None:
            return
        curr_node = self.head
        if curr_node.data == data:
            curr_node = curr_node.next
            return
        while curr_node.next is not None:
            if curr_node.next.data == data:
                curr_node.next = curr_node.next.next
                return
            curr_node = curr_node.next

    def print_list(self):
        curr_node = self.head
        while curr_node is not None:
            print(curr_node.data)
            curr_node = curr_node.next

    def get_all_data(self):
        data = []
        curr_node = self.head
        while curr_node is not None:
            data.append(curr_node.data)
            curr_node = curr_node.next
        return data
class MyLinkedList(LinkedList):

    def partition(self, data):
        # TODO: Implement me
        left = MyLinkedList(None)
        right = MyLinkedList(None)
        middle = MyLinkedList(None)
        pointer = self.head
        while pointer is not None:
            if pointer.data < data:
                left.append(pointer.data)
            elif pointer.data > data:
                right.append(pointer.data)
            else:
                middle.append(pointer.data)
            pointer = pointer.next
        
        middlePointer = middle.head
        while middlePointer is not None:
            left.append(middlePointer.data)
            middlePointer = middlePointer.next
        rightPointer = right.head
        while rightPointer is not None:
            left.append(rightPointer.data)
            rightPointer = rightPointer.next
        self = left        
        return self<jupyter_output><empty_output><jupyter_text>Unit Test **The following unit test is expected to fail until you solve the challenge.**<jupyter_code># %load test_partition.py
from nose.tools import assert_equal



class TestPartition(object):

    def test_partition(self):
        print('Test: Empty list')
        linked_list = MyLinkedList(None)
        linked_list.partition(10)
        assert_equal(linked_list.get_all_data(), [])

        print('Test: One element list, left list empty')
        linked_list = MyLinkedList(Node(5))
        linked_list.partition(0)
        assert_equal(linked_list.get_all_data(), [5])

        print('Test: Right list is empty')
        linked_list = MyLinkedList(Node(5))
        linked_list.partition(10)
        assert_equal(linked_list.get_all_data(), [5])

        print('Test: General case')
        # Partition = 10
        # Input: 4, 3, 13, 8, 10, 1, 14, 10, 12
        # Output: 4, 3, 8, 1, 10, 10, 13, 14, 12
        linked_list = MyLinkedList(Node(12))
        linked_list.insert_to_front(10)
        linked_list.insert_to_front(14)
        linked_list.insert_to_front(1)
        linked_list.insert_to_front(10)
        linked_list.insert_to_front(8)
        linked_list.insert_to_front(13)
        linked_list.insert_to_front(3)
        linked_list.insert_to_front(4)
        partitioned_list = linked_list.partition(10)
        assert_equal(partitioned_list.get_all_data(),
                     [4, 3, 8, 1, 10, 10, 13, 14, 12])

        print('Success: test_partition')


def main():
    test = TestPartition()
    test.test_partition()


if __name__ == '__main__':
    main()<jupyter_output>Test: Empty list
Test: One element list, left list empty
right
5
Test: Right list is empty
left
5
Test: General case
left
4
left
4
3
right
13
left
4
3
8
left
4
3
8
1
right
13
14
right
13
14
12
Success: test_partition
{'fraction_non_alphanumeric': 0.08430532998671195, 'fraction_numerical': 0.017569762291451352, 'mean_word_length': 2.136111111111111, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 12, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '378420', 'license': 'Apache-2.0', 'n_tokens_mistral': 2074, 'n_tokens_neox': 1964, 'n_words': 607, 'path': 'linked_lists/partition_done/partition_challenge.ipynb', 'repo_name': 'live-wire/interactive-coding-challenges', 'size': '6779'}