How to find middle element of linked list in one pass in python?
algorithm, data-structures, linked-list, list, python
Solution
I merged all the methods for you creating, finding and printing.
class Node(object):
def __init__(self, data=None, next=None):
self.data = data
self.next = next
def __str__(self):
return str(self.data)
def create_linked_list(n):
"""Creating linked list for the given
size"""
linked_list = Node(1)
head = linked_list
for i in range(2, n):
head.next = Node(i)
head = head.next
return linked_list
def print_linked_list(node):
"""To print the linked list in forward"""
while node:
print '[',node,']','[ref] ->',
node = node.next
print '-> None'
def find_middle1(node):
tick = False
half = node
while node:
node = node.next
if tick:
half = half.next
tick = not tick
return "Middle node is %s" % str(half)
def find_middle2(node):
list = []
while node:
list.append(node)
node = node.next
return "Middle node is %s" % str(list[len(list)/2])
node = create_linked_list(10)
print_linked_list(node)
print find_middle1(node)
print find_middle2(node)
Output:
[ 1 ] [ref] -> [ 2 ] [ref] -> [ 3 ] [ref] -> [ 4 ] [ref] -> [ 5 ] [ref] -> [ 6 ] [ref] -> [ 7 ] [ref] -> [ 8 ] [ref] -> [ 9 ] [ref] -> -> None
Middle node is 5
Middle node is 5
Problem
I am trying to solve a linked list problem, to find the middle element in a single pass using python. Could someone please review my code and suggest the best manner to do this? ``` class Node(object): def __init__(self, data=None, next=None): self.data = data self.next = next def __str__(self): return str(self.data) def print_nodes(node): while node: print node node = node.next def find_middle(node): while node: current = node node = node.next second_pointer = node.next next_pointer = second_pointer.next if next_pointer is None: return "Middle node is %s" % str(current) node1 = Node(1) node2 = Node(2) node3 = Node(3) node4 = Node(4) node5 = Node(5) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 print find_middle(node1) ```