Find nth to last element of a singly linked list

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

My initial thoughts:
Finding the nth to last element = Finding the (size – n + 1) first element. So we first get the size of the list and then traverse from the beginning.

My initial codes:

	public static LLNode<Integer> nthLastElement(LLNode<Integer> head, int n) {
		int size = 0;
		LLNode<Integer> current = head;
		while (current != null) {
			size++;
			current = current.getNext();
		}
		int pos = size - n + 1;
		int i = 1;
		if (pos == 1)
			return head;
		else
			current = head;
		do {
			i++;
			current = current.getNext();
		} while (current != null && i != pos);
		return current;
	}

Comments after running:

  • Works fine for most inputs. Time complexity O(n) and space complexity O(1).
  • Failed for empty list. Add one sentence after highlighted line:
    if(head == null || n < 0 || n > size) return null;

Solution:
The solution gives another insight of this question:

  1. Create two pointers, p1 and p2, that point to the beginning of the node.
  2. Increment p2 by n-1 positions, to make it point to the nth node from the beginning (to make the distance of n between p1 and p2).
  3. Check for p2->next == null if yes return value of p1, otherwise increment p1 and p2. If next of p2 is null it means p1 points to the nth node from the last as the distance between the two is n.
  4. Repeat Step 3.
	public static LLNode<Integer> nthToLast(LLNode<Integer> head, int n) {
		if (head == null || n < 1) {
			return null;
		}
		LLNode<Integer> p1 = head;
		LLNode<Integer> p2 = head;
		for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
			if (p2 == null) {
				return null; // not found since list size < n
			}
			p2 = p2.getNext();
		}
		while (p2.getNext() != null) {
			p1 = p1.getNext();
			p2 = p2.getNext();
		}
		return p1;
	}
Advertisements

2 Comments (+add yours?)

  1. Trackback: Print the last K lines of a file using C++ « Runhe Tian Coding Practice
  2. Walt
    Nov 12, 2012 @ 18:28:14

    Awesome post!

    This page also gives a good solution as well (and also the recursive solution):

    http://www.programmerinterview.com/index.php/data-structures/find-nth-to-last-element-in-a-linked-list/

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: