Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
If the list is empty, the new node IS the head — return it. Otherwise walk to the last node (the one whose next is null) and set its next to the new node, then return the original head. O(n) time without a tail pointer, O(1) with one.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you handle the empty-list case (return the new node), use the correct walk guard to land on the last node, and know that appending leaves the head unchanged.
Where candidates slip
Dereferencing a null head, walking with `while cur != null` (overshooting past the tail to null), or returning the new node instead of the original head for a non-empty list.
How to stand out
Call out the empty-list branch up front, note it's O(n) without a tail pointer, and mention that maintaining a tail makes it O(1) — exactly how a linked-list queue enqueues.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewnewNode = node(data)head == null?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Walk to the Tail and Link (Optimal without a tail pointer)
1Hint 1Explore hintHide hint
The new node has to come after every current node. If the list is empty, there's nothing to come after — what should you return?
2Hint 2Explore hintHide hint
For a non-empty list, you need the last node: the one whose next is null. How do you walk to it?
3Hint 3Explore hintHide hint
Use a pointer and loop `while cur.next != null`. When it stops, cur is the tail — set cur.next to the new node and return the original head.
A · Core idea
Build the new node, handle the empty list, then walk to the last node and attach.
The empty-list branch comes first. If head is null there's no node to attach to, and trying to walk it would dereference null. So we return the new node immediately — it becomes the sole element and the head. This branch is mandatory, unlike head insertion where the empty case folds into the general path.
Walking to the tail. For a non-empty list we start cur = head and advance while cur.next != null. The guard is the subtle part: we want to stop on the last node, not run off the end. When cur.next is null, cur is the tail. If we had looped on while cur != null, cur would end up null and we'd have nowhere to attach.
Linking and returning. Set cur.next = newNode. The new node's next is already null by construction, so it correctly becomes the new tail. We return the original head because appending never moves the head — only head insertion does that.
Why this is O(n). Reaching the tail means visiting every node. Repeated appends each pay O(n), so building a list of n elements this way is O(n²). The fix is a maintained tail pointer (see insight), which makes each append O(1).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
list = [1, 2, 3], data = 4Array state
cur on 1
1.next exists → advance
[1, 2, 3, 4]C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
If you keep a separate tail pointer alongside head, appending becomes tail.next = newNode; tail = newNode — O(1), no walk. That's exactly how a linked-list-backed queue enqueues. The walk-to-tail version is what you write when only the head is given.
ComplexityO(n) time, O(1) space — We may traverse all n nodes to reach the tail → O(n) time. A new node plus one walking pointer → O(1) extra space.
E · Edge cases and pitfalls6list = [], data = 9 — head is null → return the new node as the head → [9].Explore edge casesHide edge cases
Edge cases handled
list = [], data = 9head is null → return the new node as the head → [9].list = [5], data = 8cur.next is null immediately → 5.next = 8; return head → [5, 8].
Pitfalls
- Not handling the empty list — dereferencing head.next when head is null throws.
- Looping on `while cur != null` — cur ends at null with nowhere to attach.
- Returning newNode instead of the original head for a non-empty list.
- Appending in a loop without a tail pointer — O(n) each time, O(n²) overall.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Crashing on the empty list
If head is null, the walk loop immediately reads head.next (or cur.next) on a null reference and throws. The empty list must short-circuit by returning the new node.
Explore the code comparisonHide the code comparison
Crashing on the empty list
If head is null, the walk loop immediately reads head.next (or cur.next) on a null reference and throws. The empty list must short-circuit by returning the new node.
Don't write this
ListNode newNode = new ListNode(data);
ListNode cur = head;
while (cur.next != null) { // NPE when head == null
cur = cur.next;
}
cur.next = newNode;
return head;Write this instead
ListNode newNode = new ListNode(data);
if (head == null) {
return newNode;
}
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
return head;2Overshooting the tail
Guarding on `while cur is not None` advances cur all the way to None, so there is no node left to attach the new node to.
Explore the code comparisonHide the code comparison
Overshooting the tail
Guarding on `while cur is not None` advances cur all the way to None, so there is no node left to attach the new node to.
Don't write this
cur = head
while cur is not None: # cur ends up None
cur = cur.next
cur.next = new_node # AttributeError: None has no .nextWrite this instead
cur = head
while cur.next is not None: # stop on the last node
cur = cur.next
cur.next = new_nodeRevise
Carry the pattern into the interview
Pattern to remember
Walk to the tail, then link; special-case the empty list
Code pattern to memorize
newNode = ListNode(data)
if head is None:
return newNode
cur = head
while cur.next is not None:
cur = cur.next
cur.next = newNode
return headRules to remember
- 1Empty list is the special case: return the new node as the head — you can't dereference a null head.
- 2Walk with the guard
while cur.next != null— stop on the last node, not past it. - 3Set
tail.next = newNode; the new node's next is already null (it's the new tail). - 4Return the original head for a non-empty list — appending doesn't change the head.
- 5Without a tail pointer this is O(n); keep a tail reference if you append repeatedly to get O(1).
Use this pattern when
- Append to the back of a singly linked list, preserving insertion order (FIFO build-up)
- Building a list front-to-back as elements arrive
- Implementing a queue's enqueue when you maintain a tail pointer
- Any 'add to end' on a structure without random access to the last element
Choose another pattern when
- You append in a tight loop and care about speed → keep a tail pointer for O(1) per append
- You insert at the front → that's head insertion, O(1) with no walk
- You insert at a known index → walk to position − 1 and splice (insert at position)
Interview takeaway
Tail insertion has two cases: empty list (new node becomes head) and non-empty (walk to the last node and link). The walk is what makes it O(n); a maintained tail pointer collapses it to O(1) and turns this into a queue's enqueue.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternTail insertion: branch on the empty list, then walk to the last node and link. O(n) without a tail pointer, O(1) with one — the latter is how a linked-list queue enqueues.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Insert at the HeadPrepend instead: point the new node at the old head and return it — O(1), no walk.
- Insert at a Specific PositionWalk to position − 1 and splice; position 0 is head insert, position n is this tail append.
- Queue Using Two StacksComing soonEnqueue is a tail append; a maintained tail pointer makes it O(1) on a linked list.