Return the middle node of a given linked list.

Answer

This interview question concentrates on the developer's skills working with Java linked lists.

You are given a linked list. You need to return the middle node of the linked list. If there are two middle nodes (the list is of even size), then return the second node.

/*Example*/

Given list- 1 -> 2 -> 3 -> 4 -> 5
expected returned node- 3

Given list- 1 -> 2 -> 3 -> 4 -> 5 -> 6
expected returned node- 4

Solution:

The solution is quite simple. We will count the total number of nodes in the list. Then we will find the index of the middle element by dividing it by 2.

Let nodeCount be total number of nodes
if nodeCount is odd,
middle element is at index floor(nodeCount / 2)
for example, if nodeCount = 5, middle element element is at index floor(5 / 2) = 2
if nodeCount is even,
middle element is at index nodeCount / 2
for example, if nodeCount = 6, middle element element is at index 6 / 2 = 3

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) {
        this.val = val; 
        this.next = next; 
    }
}

class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null) return null;
        
        int nodeCount = 0;
        ListNode curr = head;
        
        while(curr != null) {
            nodeCount++;
            curr = curr.next;
        }
        
        int mid = (int) Math.floor(nodeCount / 2);
        
        curr = head;
        for (int i = 1; i <= mid; i++) {
            curr = curr.next;
        }
    
        return curr;
    }

}

Time complexity- O(nodeCount)
Space complexity- O(1)

Written by on May 21st, 2021

Next Question

How to Answer: Return the middle node of a given linked list.

Advice and answer examples written specifically for a Java Beginner Level Linked Lists job interview.

2. Return the middle node of a given linked list.

This interview question concentrates on the developer's skills working with Java linked lists.

You are given a linked list. You need to return the middle node of the linked list. If there are two middle nodes (the list is of even size), then return the second node.

/*Example*/

Given list- 1 -> 2 -> 3 -> 4 -> 5
expected returned node- 3

Given list- 1 -> 2 -> 3 -> 4 -> 5 -> 6
expected returned node- 4

Solution:

The solution is quite simple. We will count the total number of nodes in the list. Then we will find the index of the middle element by dividing it by 2.

Let nodeCount be total number of nodes
if nodeCount is odd,
middle element is at index floor(nodeCount / 2)
for example, if nodeCount = 5, middle element element is at index floor(5 / 2) = 2
if nodeCount is even,
middle element is at index nodeCount / 2
for example, if nodeCount = 6, middle element element is at index 6 / 2 = 3

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) {
        this.val = val; 
        this.next = next; 
    }
}

class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null) return null;
        
        int nodeCount = 0;
        ListNode curr = head;
        
        while(curr != null) {
            nodeCount++;
            curr = curr.next;
        }
        
        int mid = (int) Math.floor(nodeCount / 2);
        
        curr = head;
        for (int i = 1; i <= mid; i++) {
            curr = curr.next;
        }
    
        return curr;
    }

}

Time complexity- O(nodeCount)
Space complexity- O(1)

Written by S. Kumar on May 21st, 2021

Next Question