You are given the head of a singly linked list and a value x. Insert the value…
2024
You are given the head of a singly linked list and a value x. Insert the value x at the end of the linked list and return the head of the modified linked list.
Examples:
Input: LinkedList = 1 -> 2 -> 3 -> 4 -> 5, x = 6
Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Explanation: 6 is inserted at the end of the linked list.
Input: LinkedList = 4 -> 5, x = 1
Output: 4 -> 5 -> 1
Explanation: 1 is inserted at the end of the linked list.
Input format:
The first line contains a single integer n — the number of nodes in the linked list.
The second line contains n space-separated integers — the node values in order from head to tail. This line is empty when n = 0.
The third line contains a single integer x — the value to insert at the end.
Output format:
Print the values of the modified linked list in order from head to tail, separated by single spaces, on one line.
When the list is initially empty the output is the single value x.
Sample interaction (judge format):
Example 1 — stdin:
5
1 2 3 4 5
6Example 1 — stdout:
1 2 3 4 5 6Example 2 — stdin:
2
4 5
1Example 2 — stdout:
4 5 1Constraints:
0 ≤ number of nodes ≤ 104
0 ≤
node->data, x ≤ 103
Attempted by 2 students.
Show answer & explanation
Concept: A singly linked list is a chain of nodes in which every node stores a data field and exactly one pointer to the next node. The chain can be walked in one direction only, starting from head, and the last node is the unique node whose next pointer is null.
Appending therefore has no shortcut: because no node holds a reference back to the tail, the only way to attach a value at the end is to first reach that unique null-terminated node. The walk costs one visit per node, while the structural change itself is a single pointer assignment.
Application: Take head = 1 -> 2 -> 3 -> 4 -> 5 and x = 6.
Create a new node whose data field holds x and whose next pointer is null. On its own this node is already a valid one-element chain, so it can serve either as the new tail or as the whole list.
If head is null the list is empty and there is no tail to link to, so the new node is the entire list: return the new node as the head.
Otherwise place a temporary pointer curr on head. The original head must not be moved, because it is the value the function has to return.
While the next pointer of curr is not null, advance curr to that next node. The loop condition tests the next pointer rather than curr itself, so it stops with curr sitting on the last node - here the node holding 5 - instead of running past the end into null.
Set the next pointer of curr to the new node. This links 6 after 5 and makes the new node the null-terminated tail.
Return the original head. Appending never changes the first node of a non-empty list, so the head that was passed in is still the head of the result.
Cross-check: Walking the result forward from head gives 1 -> 2 -> 3 -> 4 -> 5 -> 6, which matches the expected output. Re-running the same steps on head = 4 -> 5 with x = 1 stops the loop on the node holding 5 and produces 4 -> 5 -> 1, matching the second example.
The empty-list case is handled by the early return in step 2, and that case is exactly why the routine returns a head instead of nothing: when the list starts empty the caller’s head pointer itself has to change. The traversal visits every node at most once, so the time cost grows linearly with the number of nodes while only one node is allocated, giving O(n) time and O(1) extra space.