[LinkedList] CCI 2.2-2.3

2.2 Implement an algorithm to find the kth to last element of a singly linked list.

public Node returnKthToLast(Node node, int k){
    Node n = node;
    int i = 0;
    while (n.next != null){
        if (i == k-1){
            break;
        }
        i++;
        n = n.next;
    }
    return n;
}

This was so simple, but I found out that this algorithm is not what the potential interviewer is looking for. It's more like..

int printKthToLast(Node head, int k) {
    if (head == null) {
        return 0;
    }
    int index = printKthToLast(head.next, k) + 1;
    if (index == k){
        System.out.println(k + "th to last node is " + head.data);
    }
    return index;
}

Wanted a recursive algorithm. It will take O(n), but the interviewer might want this approach. 

class Index {
    public int value = 0;
}

public Node kthToLast(Node head, int k){
    Index idx = new Index();
    return kthToLast(head, k, idx);
}

public Node kthToLast(Node head, int k, Index idx){
    if (head == null){
        return null;
    }
    Node node = kthToLast(head.next, k, idx);
    idx.value = idx.value + 1;
    if (idx.value == k){
        return head;
    }
    return node;
}

This Wrapper Class allows us to return the index as well

 

2.3 Delete Middle Node: Implement an algorithm to delete a node in the middle ( ex: any node bu the first and last node, not necessarily the exact middle) of a singly linked list, given only access to that node.

Example:

Input: the node c from the linked list a>b>c>d>e>f

Result: nothing is returned, but the new linked list looks like a > b>d>e>f

public void deleteMiddleNode(Node node){
    Node fastNode = node;
    Node slowNode = node;
    Node beforeNode = null;
    while(fastNode.next.next != null){
        fastNode = fastNode.next.next;
        beforeNode = slowNode;
        slowNode = slowNode.next;
    }
    if (beforeNode != null) {
        beforeNode.next = beforeNode.next.next;
    }
}

The solution was more simple

boolean deleteNode(Node n) {
    if (n == null || n.next == null) {
        return false;
    }
    Node next = n.next;
    n.data = next.data;
    n.next = next.next;
    return true;
}

In this problem, you are not given access to the head of the linked list. You only have access to that node. The solution is simply to copy the data from the next node over to the current node and then delete the next node.