Insertion at the Tail of a Linked List

Given the head of a singly linked list and a value, add a new node with that value at the end of the list, and return the head.

Example 1

Text

Input:  1 -> 2 -> 3, value = 4
Output: 1 -> 2 -> 3 -> 4

graph LR
    A["1"] --> B["2"] --> C["3"] --> D["4 (new)"] --> N(["null"])
    style D stroke-width:3px

Example 2

Text

Input:  empty list, value = 7
Output: 7

Insertion at the head, for comparison

Adding at the front is O(1): the new node's next becomes the old head.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static ListNode insertAtHead(ListNode head, int val) {
        return new ListNode(val, head);
    }

    public static void main(String[] args) {
        System.out.println(toList(insertAtHead(fromArray(1, 2, 3), 0)));
    }
}

Output

[0, 1, 2, 3]

The tail is harder, because a singly linked list only knows its head, so we have to walk to the end first. The nodes here are objects with a mutable next field, and null means "no next node", so no wrapper types are needed.

Brute force: recursion

Think about the list as "a head node, followed by a smaller list":

If the list is empty (null), the result is the new node.
Otherwise, insert into the rest of the list (head.next), reattach the result, and return the node.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static ListNode insertAtTail(ListNode head, int val) {
        if (head == null) return new ListNode(val, null);
        head.next = insertAtTail(head.next, val);
        return head;
    }

    public static void main(String[] args) {
        System.out.println(toList(insertAtTail(fromArray(1, 2, 3), 4)));
        System.out.println(toList(insertAtTail(null, 7)));
    }
}

Output

[1, 2, 3, 4]
[7]

Time: O(n). Space: O(n) for the call stack, with one frame per node. A list with a few hundred thousand nodes could throw StackOverflowError.

Optimal: walk to the last node

cur starts at head, and each step moves it to cur.next. When cur.next is null, cur is the last node, and we assign the new node to cur.next.

Walkthrough with 1 -> 2 -> 3, value 4:

step	`cur`	`cur.next`	action
1	node 1	node 2	move `cur` forward
2	node 2	node 3	move `cur` forward
3	node 3	`null`	set `cur.next` to the new node

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static ListNode insertAtTail(ListNode head, int val) {
        ListNode node = new ListNode(val, null);
        if (head == null) return node; // empty list: the new node is the head
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
        return head;
    }

    public static void main(String[] args) {
        System.out.println(toList(insertAtTail(fromArray(1, 2, 3), 4)));
        System.out.println(toList(insertAtTail(null, 7)));
    }
}

Output

[1, 2, 3, 4]
[7]

Time: O(n). Space: O(1).

The empty list needs a special case: there is no last node to attach to, so the new node becomes the head. A dummy node placed before the head, as in the last example below, removes that case.

Appending many values: keep a tail reference

Calling insertAtTail n times walks the list n times, which is O(n²) in total. When building a list, keep a reference to the last node instead, so each append is O(1):

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static ListNode build(int[] values) {
        ListNode dummy = new ListNode(0, null);
        ListNode tail = dummy;
        for (int val : values) {
            tail.next = new ListNode(val, null);
            tail = tail.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        System.out.println(toList(build(new int[]{1, 2, 3, 4})));
    }
}

Output

[1, 2, 3, 4]

A list class can also store a permanent tail field for O(1) appends. Two references to the same node are allowed in Java, so the tail field and the previous node's next can both point at the last node. The class must then update tail on every append and on every removal of the last node.

Edge cases

Empty list: the new node becomes the head.
One-node list: the loop runs once.