Given a singly-linked list, find the middle node of the list. If the list contains an even number of nodes, return the second middle node.
Table of Contents
Sample Input:
1 -> 2 -> 3 -> 4 -> 5
Expected Output:
3
In this example, the linked list has an odd number of nodes, and the middle node is 3.
Sample Input:
1 -> 2 -> 3 -> 4 -> 5 -> 6
Expected Output:
4
In this example, the linked list has an even number of nodes, and there are two middle nodes: 3 and 4. The function should return the second middle node, which is 4.
Time and Space Complexity:
The time complexity of the algorithm is O(n) because we need to traverse the entire linked list once to find the middle node. The space complexity is O(1) as we are using only a constant amount of additional memory.
Now, let’s provide the C++ solution with comments explaining the code:
#include <iostream>
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* findMiddle(ListNode* head) {
// Initialize two pointers: slow and fast
ListNode* slow = head;
ListNode* fast = head;
// Traverse the linked list with two pointers
while (fast != nullptr && fast->next != nullptr) {
// Move slow pointer one step at a time
slow = slow->next;
// Move fast pointer two steps at a time
fast = fast->next->next;
}
// At this point, the slow pointer will be pointing to the middle node
return slow;
}
int main() {
// Create the linked list for the sample input
ListNode* node1 = new ListNode(1);
ListNode* node2 = new ListNode(2);
ListNode* node3 = new ListNode(3);
ListNode* node4 = new ListNode(4);
ListNode* node5 = new ListNode(5);
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
// Find the middle node of the linked list
ListNode* middleNode = findMiddle(node1);
std::cout << "The middle node value is: " << middleNode->val << std::endl;
// Don't forget to free the allocated memory
delete node1;
delete node2;
delete node3;
delete node4;
delete node5;
return 0;
}
The findMiddle function uses two pointers, slow and fast, to find the middle node of 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 pointing to the middle node.
In the given example, the function will correctly find the middle node with value 3, and the output will be 3.
The time complexity of this approach is O(n) because in the worst case, the fast pointer will traverse the entire linked list. The space complexity is O(1) as we are using only two pointers regardless of the size of the input linked list.