712529. Array to Linked List
Array to Linked List
Slug: introduction-to-linked-list
Difficulty: Easy
Id: 712529
Topic Tags: Linked List, Data Structures
Company Tags: None
Summary
This problem requires converting an array into a linked list. The input is an array of elements and the output should be a linked list where each node contains the corresponding element from the array. This problem involves understanding the basics of linked lists and arrays.
Detailed Explanation
To convert an array to a linked list, we need to create a new linked list and iterate over the array. For each element in the array, we create a new node with the current value and add it to the end of the linked list. We also keep track of the head of the linked list.
Here is the step-by-step breakdown:
- Create an empty linked list.
- Iterate over the array.
- For each element in the array:
- Create a new node with the current value.
- Add the new node to the end of the linked list.
- Return the head of the linked list.
The time complexity for this solution is O(n), where n is the number of elements in the array, as we are iterating over the array once. The space complexity is also O(n) as we are creating a new linked list with n nodes.
Optimized Solutions
Java
public class ArrayToLinkedList {
public static Node arrayToLinkedList(int[] arr) {
Node head = null;
for (int val : arr) {
head = addNode(head, val);
}
return head;
}
private static Node addNode(Node head, int val) {
Node node = new Node(val);
if (head == null) {
head = node;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
return head;
}
public static class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
}
}