Inserting a node to a given position in a linked list

Given


You’re given the pointer to the head node of a linked list, an integer to add to the list and the position at which the integer must be inserted. Create a new node with the given integer, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is empty.

Solution

Node InsertNth(Node head, int data, int position) {
    Node newNode = new Node();
    newNode.data = data;
    newNode.next = null;

    if (head == null) {
        return newNode;
    }
    if (position == 0) {
        newNode.next = head;
        head = newNode;
        return head;
    }
    Node prev = null;
    Node current = head;
    int i = 0;
    while (current !=null && i < position) {
        prev = current;
        current = current.next;
        i++;
    }
    newNode.next = prev.next;
    prev.next = newNode;
    return head;
}

The code works fine. But I strongly feel that there is a chance of improvement. I see a lot of checks here, how can I reduce those and make my code more readable and covering all the edge cases?

Also, is there any recursive version possible for the given code because list is a recursive data structure hence, there should be some recursive way, right?

I see a lot of checks here, how can I reduce those and make my code more readable and covering all the edge cases?

Using a dummy node that points to the head can help reduce many of the checks:

Node insertNth(Node head, int data, int position) {
    Node dummy = new Node();
    dummy.next = head;

    Node runner = dummy;
    for (int i = 0; i < position; ++i) {
        runner = runner.next;
    }

    Node node = new Node();
    node.data = data;
    node.next = runner.next;
    runner.next = node;

    return dummy.next;
}

Also, is there any recursive version possible for the given code because list is a recursive data structure hence, there should be some recursive way, right?

Naturally, a recursive solution is also possible:

Node insertNthRecursive(Node head, int data, int position) {
    if (position == 0) {
        Node node = new Node();
        node.data = data;
        node.next = head;
        return node;
    }
    head.next = insertNthRecursive(head.next, data, position - 1);
    return head;
}

Update

As @PeterCordes pointed out, the above implementation is a bit dirty,
as it rewrites the links unnecessarily.
Here's a variant replacing the head.next = ... line above to make it cleaner.

Node next = insertNthRecursive(head.next, data, position - 1);
    if (position == 1) {
        head.next = next;
    }

Input validation

I intentionally omitted input validation from these example implementations:
they won't work with position values outside the range \$[0, n]\$.
I leave that fun up to you.

StackExchange Code Review Q#104940, answer score: 7