700525. Linked List Insertion At End
Linked List Insertion At End
Slug: linked-list-insertion-1587115620
Difficulty: Basic
Id: 700525
Topic Tags: Linked List, Data Structures
Company Tags: Hike, Wipro, TCS
Summary
Inserting a new node at the end of a singly linked list is a fundamental operation in data structures. Given the head of the linked list and the value to be inserted, we need to update the list by adding the new node as the last element.
This problem requires understanding of basic linked list concepts, including node structure, insertion, and traversal.
Detailed Explanation
The solution involves creating a new node with the given value and updating the existing nodes in the list. We start by traversing the list until we reach the last node (or the end of the list). Once we find the last node, we update its next pointer to point to the new node.
Here's a step-by-step breakdown:
- Start at the head of the linked list.
- Traverse the list until you reach the last node (i.e.,
current->next == NULL). - Create a new node with the given value.
- Update the
nextpointer of the last node to point to the new node.
Time complexity: O(n), where n is the length of the linked list. Space complexity: O(1), as we only use a constant amount of space to store the new node and traversal variables.
ASCII Art Diagram
A -> B -> C (initial list)
|
v
D (new node)
A -> B -> C -> D (final list)
Optimized Solutions
Java
public Node insertAtEnd(Node head, int val) {
Node newNode = new Node(val);
if (head == null) {
return newNode;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
return head;
}