700040. Node at a given index in linked list
Here is the detailed Markdown blog post for the problem "Node at a given index in linked list":
Node at a given index in linked list
Summary
Given a singly linked list and an integer index, find the node at that index. The indexing starts from 0, so if the index is 0, we return the head of the linked list.
This problem involves manipulating a linked list data structure, which requires understanding how to traverse and locate nodes in the list.
Detailed Explanation
To solve this problem, we can use a simple traversal approach. We start at the head of the linked list and keep moving forward until we reach the desired index. If the index is 0, we return the head of the list. Otherwise, we increment our index and move to the next node in the list.
Here's the step-by-step breakdown:
- Start at the head of the linked list.
- Initialize an index variable to the given index.
- While the index is greater than 0:
- Move to the next node in the list.
- Decrement the index by 1.
- If the index reaches 0, return the current node (the desired node at the given index).
Time complexity: O(n), where n is the length of the linked list. This is because we traverse the entire list once.
Space complexity: O(1), since we only use a constant amount of space to store the index and the current node.
Optimized Solutions
Java
public class NodeAtGivenIndex {
public static Node getNode(Node head, int index) {
Node current = head;
int i = 0;
while (current != null && i < index) {
current = current.next;
i++;
}
return current;
}
}