Middle Element Of Linked List

 Let's solve a question from LeetCode called "Middle of the Linked List" (LeetCode problem #876) using the concept of finding the middle element of a linked list.

Problem Statement: Given a non-empty, singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

Example: Input: 1 -> 2 -> 3 -> 4 -> 5 Output: Node with value 3

To solve this problem, we can use the "slow and fast pointer" approach. We'll use two pointers, a slow pointer and a fast pointer, to traverse the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

Here's the complete code to solve the problem:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def find_middle_node(head):
    # Initialize the slow and fast pointers to the head of the linked list
    slow = head
    fast = head

    # Traverse the linked list using the slow and fast pointers
    while fast and fast.next:
        # Move the slow pointer one step at a time
        slow = slow.next
        # Move the fast pointer two steps at a time
        fast = fast.next.next

    # Return the middle node
    return slow


# Example usage
# Create a linked list with nodes [1, 2, 3, 4, 5]
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# Find the middle node
middle_node = find_middle_node(head)

# Print the value of the middle node
print(middle_node.val)

In this code, we create a linked list with nodes [1, 2, 3, 4, 5]. We then call the find_middle_node function, passing the head of the linked list as input. The middle node is retrieved using the slow and fast pointers, and its value is printed as "3".

Time and Space Complexity Analysis: The time complexity of this solution is O(N), where N is the number of nodes in the linked list. We traverse the linked list once, and the slow pointer moves one step at a time, while the fast pointer moves two steps at a time. Therefore, the time complexity is linear with respect to the number of nodes in the list.

The space complexity is O(1) because we are using a constant amount of extra space to store the slow and fast pointers. The space required does not depend on the size of the input list.