Traverse the linked list and store each node in an array. Then return the node at the middle index (length // 2).
Use two pointers: slow moves one step at a time, fast moves two steps. When fast reaches the end, slow is at the middle.
""" 0876.1 - Solution 1 - Array Approach """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional, List
#####################################################################################
# Classes
#####################################################################################
class ListNode:
"""ListNode Class"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""Solution Class"""
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
"""Middle Node Function"""
arr = []
curr = head
while curr:
arr.append(curr)
curr = curr.next
return arr[len(arr) // 2]
#####################################################################################
# Functions
#####################################################################################
def build_list(vals: List[int]) -> Optional[ListNode]:
"""Helper to build a linked list from a list of values"""
dummy = ListNode(0)
curr = dummy
for v in vals:
curr.next = ListNode(v)
curr = curr.next
return dummy.next
def print_list(node: Optional[ListNode]) -> None:
"""Helper to print a linked list"""
vals = []
while node:
vals.append(node.val)
node = node.next
print(vals)
def testcase():
"""Test Function"""
print_list(Solution().middleNode(build_list([1, 2, 3, 4, 5]))) # [3, 4, 5]
print_list(Solution().middleNode(build_list([1, 2, 3, 4, 5, 6]))) # [4, 5, 6]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0876.2 - Solution 2 - Two Pointer (Slow & Fast) """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional, List
#####################################################################################
# Classes
#####################################################################################
class ListNode:
"""ListNode Class"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
"""Solution Class"""
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
"""Middle Node Function"""
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
#####################################################################################
# Functions
#####################################################################################
def build_list(vals: List[int]) -> Optional[ListNode]:
"""Helper to build a linked list from a list of values"""
dummy = ListNode(0)
curr = dummy
for v in vals:
curr.next = ListNode(v)
curr = curr.next
return dummy.next
def print_list(node: Optional[ListNode]) -> None:
"""Helper to print a linked list"""
vals = []
while node:
vals.append(node.val)
node = node.next
print(vals)
def testcase():
"""Test Function"""
print_list(Solution().middleNode(build_list([1, 2, 3, 4, 5]))) # [3, 4, 5]
print_list(Solution().middleNode(build_list([1, 2, 3, 4, 5, 6]))) # [4, 5, 6]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()