700665. Insert in Middle of Linked List
Basic
Insert in Middle of Linked List
Slug: insert-in-middle-of-linked-list
Difficulty: Basic
Id: 700665
Topic Tags: Linked List, Data Structures
Company Tags: None
Summary
The problem is to insert a new node into the middle of a linked list. The key concepts involved are basic data structures and algorithms, particularly linked lists.
Detailed Explanation
To solve this problem, we will first need to find the middle of the linked list. We can do this by iterating through the list until we reach the halfway point. Once we have found the middle, we can insert our new node into the list at that position.
Here is a step-by-step breakdown of the solution:
- Initialize two pointers,
slowandfast, to the beginning of the linked list. - Iterate through the list until
fastreaches the end of the list. For each iteration:- Move
slowone node forward. - Move
fasttwo nodes forward (if there is an odd number of nodes, this will still point to the correct position).
- Move
- Once
fasthas reached the end of the list,slowwill be pointing to the middle node. Insert our new node afterslow.
Optimized Solutions
Java
public class Solution {
public void insertInMiddle(Node head, int data) {
if (head == null || head.next == null) {
return; // list has only one or zero nodes
}
Node slow = head;
Node fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
Node newNode = new Node(data);
newNode.next = slow.next;
slow.next = newNode;
}
}