876. Middle of the Linked List

 

LeetCode Solution: Find the Middle of a Linked List in JavaScript

Finding the middle node of a singly-linked list is a common problem on LeetCode. In this post, we will walk through the intuition, approach, and complexity of solving this problem using JavaScript. Below is the complete code solution, along with an explanation.

Intuition

To find the middle node of a linked list efficiently, we can use the two-pointer technique. By using two pointers, slow and fast, where slow moves one step at a time and fast moves two steps at a time, we can ensure that when fast reaches the end of the list, slow will be at the middle. This method allows us to determine the middle node in a single pass through the list.

Approach

  1. Initialize Two Pointers:

    • Initialize slow and fast pointers to the head of the linked list.

  2. Traverse the List:

    • Use a while loop to move slow one step at a time and fast two steps at a time.

    • Continue the loop until fast reaches the end of the list or fast.next is null.

  3. Return the Middle Node:

    • When the loop exits, slow will be at the middle node of the list.

    • Return the slow pointer.

Code

Here’s the complete JavaScript code for finding the middle node of a singly-linked list:

javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let slow = head;
    let fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

Complexity

  • Time Complexity: O(n), where n is the number of nodes in the linked list. The function makes a single pass through the list.

  • Space Complexity: O(1), as we are using a constant amount of extra space for the slow and fast pointers.

Example

Here’s how you can use this function:

javascript
// Define the ListNode class
function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

// Create a linked list: 1 -> 2 -> 3 -> 4 -> 5
let head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

// Find the middle node
let middle = middleNode(head);
console.log(middle.val);  // Output: 3

Conclusion

This approach provides an efficient and straightforward solution to finding the middle node of a singly-linked list. By using the two-pointer technique, we can determine the middle node in linear time with constant space complexity.

For more detailed explanations and additional solutions, check out my solution on LeetCode: Middle of the Linked List - LeetCode

I hope this guide helps you understand how to solve the problem of finding the middle node in a linked list using JavaScript. Happy coding! šŸš€

If you have any questions or need further clarification, feel free to ask in the comments below!

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

14. Longest Common Prefix

  Finding the Longest Common Prefix in JavaScript When working with arrays of strings, a common problem is finding the longest common prefix among these strings. The longest common prefix is the initial portion of all strings in the array that is identical. This is a frequent problem on coding platforms like LeetCode, and it's essential to understand how to tackle it efficiently. In this blog post, we'll dive into the intuition, approach, and complexity of finding the longest common prefix in JavaScript. Intuition The intuition behind finding the longest common prefix is simple. By sorting the array of strings lexicographically (alphabetically), we can bring the smallest and largest strings to the beginning and end of the array. The common prefix between the first and last string in this sorted array will give us the longest common prefix for the entire array. This approach leverages the natural order of strings to simplify our task. Approach Sort the Array : First, we sort the...
Read more