Analysis

As usual in linked list questions, if the interviewer does not specify the type of linked list, make sure you clarify. In this case it is a singly linked list as the question has very little depth otherwise. Now let’s clarify the problem, with an input of k=1, the last element should be returned; with k=2, the second last element; and on so on.

With a singly linked list, it’s easy to solve the problem using two iterations by counting the length of the list in the first iteration and using the second iteration to pinpoint the desired element. Is there a better solution?

The solution your interviewer is likely after is to have two pointers; one that starts iterating through the list immediately, and one that is delayed k times before iterating. Once the first pointer reaches the end, the second pointer will either be the kth last element, or it will not be initialised, meaning that the list was not of sufficient length.

Complexity

Since there are a constant amount of pointers iterating through the list a single time, the complexity is O(n).

Really there is minimal difference in the two iteration and single iteration solutions presented above in terms of time complexity since both run in linear time. In fact, the two iteration solution is likely to perform better when k > n / 2 since the single iteration version is incrementing two pointers in the second portion of the loop.

One difference that could affect performance though is that with a sufficiently large linked list, the single iteration solution will utilise the CPU cache better as it only iterates through a single time. Whether this means it’s a better solution depends on both the expected size of n and how the data structure is implemented (potentially what language too).

Code

/**
 * Gets the kth last element of a linked list.
 *
 * @param head The head of the linked list.
 * @param k The number of elements to count backward.
 * @return The kth last element of the linked list, if it is not large
 * enough, return 0.
 */
public static LinkedList getKthLastElement(LinkedList head, int k) {
    if (head == null || k < 1) {
        return null;
    }

    LinkedList current = head;
    LinkedList nBehindCurrent = head;

    for (int i = 0; i < k - 1; i++) {
        current = current.next;
        if (current == null) {
            return null;
        }
    }

    while (current.next != null) {
        nBehindCurrent = nBehindCurrent.next;
        current = current.next;
    }

    return nBehindCurrent;
}

/**
 * Gets the kth last element of a {@link SinglyLinkedList}.
 *
 * @param {SinglyLinkedList} head The head of the list.
 * @param {number} k The number of elements to count backward.
 * @returns The kth last element of the linked list, if it is not large enough,
 * return 0.
 */
function getKthLastElement(head, k) {
  if (!head || k < 1) {
    return undefined;
  }

  var current = head;
  var nBehindCurrent = head;

  for (var i = 0; i < k - 1; i++) {
    current = current.next;
    if (!current) {
      return undefined;
    }
  }

  while (typeof current.next !== 'undefined') {
    nBehindCurrent = nBehindCurrent.next;
    current = current.next;
  }

  return nBehindCurrent;
}

/**
 * Creates a singly linked list node.
 *
 * @constructor
 * @param {Object} data The data associated with this node.
 * @param {SinglyLinkedList} next The next node in the linked list.
 */
function SinglyLinkedList(data, next) {
  this.data = data;
  this.next = next;
}

Textbooks

Here are two textbooks that provide many Q&A's like this post that I personally recommend, both were invaluable to me when I was studying for my interviews.

 

More posts tagged Interview question