Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Linked List

Middle of a Linked List

Easy · Linked List · Asked at Amazon, Microsoft, TCS, Infosys, Wipro

Print the value of the middle node. If there are two middle nodes, print the second one.

Input

First line: n. Second line: the n node values from head to tail.

Output

The middle value.

Constraints

Slow and fast pointers: when fast reaches the end, slow is at the middle.

Example 1

Input

5
1 2 3 4 5

Output

3

Example 2

Input

6
1 2 3 4 5 6

Output

4

Hints

  1. Counting the nodes and walking n/2 steps takes two passes. Can you do it in one?
  2. Move slow by 1 and fast by 2. When fast can't move any more, slow is at the middle.

Approach

Tortoise and hare. Both start at head. While fast and fast.next exist, move slow = slow.next and fast = fast.next.next. Fast covers twice the distance, so slow ends at the middle. For an even length it stops on the second middle node, which is what's asked.

Complexity: O(n) time · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long val;
    Node *next;
    Node(long long v) : val(v), next(nullptr) {}
};

int main() {
    int n;
    cin >> n;
    Node dummy(0), *tail = &dummy;
    for (int i = 0; i < n; i++) {
        long long v;
        cin >> v;
        tail = tail->next = new Node(v);
    }
    Node *slow = dummy.next, *fast = dummy.next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    cout << slow->val << "\n";
    return 0;
}

Python solution

import sys


class Node:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt


data = sys.stdin.read().split()
n = int(data[0])
head = None
for v in reversed(data[1 : n + 1]):
    head = Node(v, head)

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
print(slow.val)

Java solution

import java.util.*;

public class Main {
    static class Node {
        long val;
        Node next;
        Node(long v) { val = v; }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node dummy = new Node(0), tail = dummy;
        for (int i = 0; i < n; i++) tail = tail.next = new Node(sc.nextLong());
        Node slow = dummy.next, fast = dummy.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        System.out.println(slow.val);
    }
}

Solve Middle of a Linked List online · All practice problems