Insert a Node at the End of a Linked List
Solve this Problemhead of a singly linked list and an integer val, insert a new node holding val at the very end of the list, and return the head of the resulting list.
Unlike inserting at the front, appending at the end can't skip straight to the answer — a singly linked listSingly Linked ListA chain of nodes connected only through each node's next pointer, in one direction. There's no way to jump directly to the last node — the only way to find it is to follow next pointers from the head, one node at a time. only has forward next pointers, so the last node has to be located by walking from head. Once found, attaching the new node there is a single pointer write. Remember to handle the empty list: if head is null, the new node becomes the entire list.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes in head ≤ 10⁴ - ◆
-10⁹ ≤ node value, val ≤ 10⁹ - ◆
Handle the empty-list case — inserting into head = [] must return a one-node list
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public Node insertAtEnd(Node head, int val) { |
| 3 | Node newNode = new Node(val); |
| 4 | if (head == null) { |
| 5 | return newNode; |
| 6 | } |
| 7 | Node curr = head; |
| 8 | while (curr.next != null) { |
| 9 | curr = curr.next; |
| 10 | } |
| 11 | curr.next = newNode; |
| 12 | return head; |
| 13 | } |
| 14 | } |
| 15 |
4Create a new node holding 4. It isn't linked into the list yet.
Approach & Solutions
Brute Force — Copy to Array, Append, Rebuild List
BruteWalk the existing list into a plain array, then append val onto the end of that array. Throw the entire original list away and build a brand-new list from the array using a dummy + tail pointer. Correct, but every existing node is read and re-allocated even though only one new node actually needed to be added.
O(n)O(n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node insertAtEnd(Node head, int val) {
9 List<Integer> vals = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 vals.add(curr.val);
13 curr = curr.next;
14 }
15 vals.add(val);
16 Node dummy = new Node(0);
17 Node tail = dummy;
18 for (int v : vals) {
19 tail.next = new Node(v);
20 tail = tail.next;
21 }
22 return dummy.next;
23 }
24}Optimal — Traverse to the Last Node, Attach There
OptimalA singly linked list only has forward next pointers, so the last node still has to be found by walking from head. But once found, the new node is attached with a single pointer write — no copying, no second list. Handle the empty-list case separately: if head is null, the new node simply becomes the whole list.
O(n)O(1) extra1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node insertAtEnd(Node head, int val) {
9 Node newNode = new Node(val);
10 if (head == null) {
11 return newNode;
12 }
13 Node curr = head;
14 while (curr.next != null) {
15 curr = curr.next;
16 }
17 curr.next = newNode;
18 return head;
19 }
20}