Full Beginner Python Explanation, 3 methods
First, let\'s start with the simplest solution \u2013 storing all the nodes in a list and then accessing the middle node. Working with lists is typically more i
First, let\'s start with the simplest solution \u2013 storing all the nodes in a list and then accessing the middle node. Working with lists is typically more intuitive than linked lists since we learn them first and they easily allow us to get their length. Once we have this method down, we can think about how to move forward and find better solutions!\n\n**Method 1: Using list; Time: O(N), Memory: O(N)**\n```\ndef middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\n\tnodes = [] #array to keep track of the nodes\n\twhile head:\n\t\tnodes.append(head) #add the nodes to our array\n\t\thead = head.next\n\tmiddle = len(nodes)//2 # get the middle index of the array\n\treturn nodes[middle] #return the node in the middle\n```\nMany linked list problems can be solved by storing all the nodes in a list and then completing the problem as if all the values were stored in a list from the beginning. Using the built in length function for arrays, ```len()```, we can easily access the node in the middle by indexing ```len(nodes)//2```.\n\n**Moving on from the list solution**\nGenerally, solving linked list problems by storing all the nodes in a list is discouraged since it removes the whole challenge of solving it using linked lists. In this specific example, our method 1 takes a lot of extra space, on the order of ```O(N)```, and we can typically solve linked list problems with much less storage. To find the solution, let\'s identify the main reason we resorted to using a regular list in the first place \u2013\u2013 to find the length. Instead of doing it this way, we can find the length of the linked list by just running all the way through the list and keeping track of how many nodes we go through!\n\n**Method 2: Find Length; Time: O(N); Memory: O(1)**\n```\ndef middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\n\trunner = head #runner to find the length of the linked list\n\tlength = 0 #length of list\n\twhile runner:\n\t\tlength += 1 #add 1 to the length whenever we still have a node\n\t\trunner = runner.next\n\tfor i in range(length//2): #go halfway through the linked list\n\t\thead = head.next\n\treturn head #return the middle node\n```\nIn this method we use ```runner``` to find the length of the list, stored in ```length```. Then we start again at the ```head``` and go halfway through the list by calling ```head = head.next``` a total of ```length//2``` times. This is a great solution since it is solved in ```O(N)``` time and with constant space. However, we aren\'t quite doing this in one-pass --> we end up going through the full linked list and then we need to go halfway through once again. \n\nSo, how can we do this in one pass? Well, many linked list problems can be solved with a smart use of 2 or 3 pointers, and this problem is no exception. To get halfway through the linked list, we can use one pointer to go through the list twice as quickly as the other!\n\n**Method 3: Two Pointers; Time: O(N), Memory: O(1)**\n```\ndef middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\n\tslow = head #this will go forward 1 at a time\n\tfast = head #move forward 2 at a time\n\twhile fast and fast.next: #while our fast node exists and isn\'t the last node\n\t\tslow = slow.next #slow pointer moves forward just 1 spot\n\t\tfast = fast.next.next #fast pointer moves forward by two\n\treturn slow #slow should be in the middle!\n```\nBy the time the ```fast``` pointer makes it to the end of the list, ```slow``` will be right in the middle since the ```fast``` pointer goes through the list twice as quickly as the ```slow``` pointer. \n\n**Thanks for Reading!**\nIf this post has been helpful, please consider upvoting! Also, if I made any mistakes or there are other optimizations, methods I didn\'t consider, etc. please let me know!
['Two Pointers', 'Python']