Middle of the Linked List

Clarify the problem:

• The problem requires finding the middle node of a linked list.
• We need to implement a function that takes the head of a linked list as input and returns the middle node.

Analyze the problem:

• Input: The head node of a linked list.
• Output: The middle node of the linked list.
• Constraints:
  • The linked list may contain an odd or even number of nodes.
  • If the linked list has an odd number of nodes, the middle node is the one located at index length // 2 (0-based indexing).
  • If the linked list has an even number of nodes, the middle node is the second node located at index length // 2 (0-based indexing).

Design an algorithm:

• We can solve this problem using the slow and fast pointer approach.
• Initialize two pointers, slow and fast, both pointing to the head of the linked list.
• Move the fast pointer two steps at a time and the slow pointer one step at a time.
• When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle node.

Explain your approach:

• We will implement a function called middleNode that takes the head of a linked list as input.
• Initialize two pointers, slow and fast, both pointing to the head of the linked list.
• Iterate through the linked list while moving the fast pointer two steps at a time and the slow pointer one step at a time.
• When the fast pointer reaches the end of the linked list, return the node pointed to by the slow pointer.

Write clean and readable code:

python

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

def middleNode(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Test your code:

python

# Test case 1
# Input: 1 -> 2 -> 3 -> 4 -> 5
# The middle node is 3.
# Expected output: 3
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)
assert middleNode(head).val == 3

# Test case 2
# Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6
# The middle node is 4.
# Expected output: 4
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)
head.next.next.next.next.next = ListNode(6)
assert middleNode(head).val == 4

Optimize if necessary:

• The current solution has a time complexity of O(n), where n is the number of nodes in the linked list.
• This is because we traverse the linked list once using the slow and fast pointer approach.
• The space complexity is O(1) since we only use a constant amount of extra space for the slow and fast pointers.

Handle error cases:

• The code assumes that the input is a valid linked list.
• It does not handle cases where the input is None or if the linked list is empty.
• Additional checks can be added at the beginning of the middleNode function to handle these cases gracefully.

Discuss complexity analysis:

• The time complexity of the solution is O(n), where n is the number of nodes in the linked list.
• The space complexity is O(1) since we only use a constant amount of extra space for the slow and fast pointers.
• The solution traverses the linked list only once, making it efficient in terms of time complexity.