Delete node in LinkedList

Delete a given node in a singly linked list. You don't have an access to the root node of the list. You have only access to the given node. Let's suppose this is your definition of a node.

class Node {
    Node next;
    int data;
}

Deleting a node in the middle of a singly linked list could happen if you copy the value from the next node over the given node and then to delete the next node.

public static void deleteMiddleNode(Node n){
    if(n == null){
        System.out.println("Node value is incorrect");
    }
    // in case of last element
    if(n.next == null){
        n = null;
    }
  
    Node next = n.next;
    n.data = next.data;
    n.next = next.next;
}

Reverse a LinkedList

Given a singly linked list. You have to revers it.

The first solution uses recursion.

Node reverseList(Node previous, Node current) {
    Node tmp;
    if (current.next == null) {
        current.next = previous;
        return current;
    }
    tmp = reverseList(current, current.next);
    current.next = previous;
    return tmp;
}

The second solution is non-recursive.

Node reverse(Node current) {
    Node tmp;
    Node previous = null;
    while (current != null) {
        tmp = current.next;
        current.next = previous;
        previous = current;
        current= tmp;
    }
    return previous;
}

How to find k-th element from the end of a linked list?

The solution below uses recursion to get the number of elements in the linked list and then prints only the value at the k-th node from end of the Linked List.

public static void kthElement(LinkedList list, int k) {
    ListIterator iterator = list.listIterator();
    handleNextElement(iterator, k);
}

private static int handleNextElement(ListIterator iterator, int k) {
    int elementValue = 0;
    if (!iterator.hasNext()) {
        return 0;
    }

    elementValue = iterator.next();
    int count = handleNextElement(iterator, k) + 1;

    if (count == k) {
        System.out.println(elementValue);
    }

    return count;
}

k-th node from end

Another solution is non-recursive where you run two runners/iterators in parallel with distance k between them.

Integer kthElement(LinkedList list, int k) {
    if (k < 1 || k > list.size()) {
        return null;
    }

    ListIterator iterator = list.listIterator();
    for (int i = 0; i < k; i++) {
        if (iterator.hasNext()) {
            iterator.next();
        } else {
            return null;
        }
    }

    ListIterator iterator2 = list.listIterator();
    while (iterator.hasNext()) {
        iterator.next();
        iterator2.next();
    }

    Integer result = iterator2.next();
    return result;
}

2 iterators with distance k between them

This solution takes O(n) time and O(1) space.

Cycle in LinkedList

There is an interesting technique how you can verify if there is a cycle in a LinkedList without using any additional data structure. All that is needed are two references (fast runner and slow runner) of the same type as the elements in the linked list. Here is the solution:

boolean hasCycle(Node linkedList) {
    if (linkedList == null) {
        return false;
    }
    Node n1, n2;
    n1 = linkedList;
    n2 = linkedList.getNext();
    while (n1 != null && n2 != null) {
        if (n1.equals(n2)) {
            return true;
        }

        n1 = n1.getNext();
        if (n2.getNext() != null) {
            n2 = n2.getNext().getNext();
        } else {
            return false;
        }

    }
    return true;
}