China Cat my RAM

Singly Linked List – mth to the last element

Example Problem:
Given a singly-linked list, devise a time- and space-efficient algorithm to find the mth-to-last element of the list. Implement your algorithm, taking care to handle relevant error conditions. Define mth to last such that when m = 0, the last element of the list is returned. 1->3->6->7->8->9->13

Java's LinkedList class, which is an implementation of a doubly linked list, would make this task trivial, so that is exactly why it must be done in a singly linked list. Here is my implementation in Java.

First I would create a Java object representing an element in a singly linked list.

public class SinglyLinkedListElement {
	private int data;
	private SinglyLinkedListElement next;

	public SinglyLinkedListElement(int data) {
		this.data = data;
		next = null;
	}
	public int getValue() {
		return this.data;
	}
	public SinglyLinkedListElement getNext() {
		return this.next;
	}
	public void setNext(SinglyLinkedListElement next) {
		this.next = next;
	}
}

Now I'll (1) instantiate a SinglyLinkedListElement for each test integer creating a singly linked list and (2) find the element that is mth from the last. In this case, m is hard-coded to be 3 below.

public static void getMthToLastElementInSinglyLinkedList() {

    int[] testData = new int[]{1, 3, 6, 7, 8, 9, 13};

    SinglyLinkedListElement head = null;
    SinglyLinkedListElement prevElem = null;
    for (int i = 0; i < testData.length; i++) {
    	SinglyLinkedListElement newElem = new SinglyLinkedListElement(testData[i]);
    	if (head == null) {
    	    head = newElem;
    	}
    	else {
    	    prevElem.setNext(newElem);
    	}
    	prevElem = newElem;
    }
    final int M = 3;

    //advanced the head to at least M
    SinglyLinkedListElement curr = head;
    for (int i = 0; i < M; i++) {
    	if (curr.getNext() != null) {
    		curr = curr.getNext();
    	}
    	else {
    		int listCount = i + 1;
    		System.out.println("Not enough items in list");
    	}
    }

    SinglyLinkedListElement mBehind = head;
    while (curr.getNext() != null) {
    	mBehind = mBehind.getNext();
    	curr = curr.getNext();
    }
    System.out.println("Value of mBehind is " + mBehind.getValue());
}

Reference: Programming Interviews Exposed (provides a solution in C)