How would you get the nth node from the tail in a

Question

So I got this question from an exam.

How would you get the nth node from the tail in a singly linked list?

Each Node has a value and a next (which is a pointer to the next value). We are given this:

getNodeFromTail(Node head, int x) {

}

So the way I did it is to find the length of the list by traversing it once. Then going again to get the (length - x) node. So in total, 2 traversals.

getNodeFromTail(Node head, int x) {
    int length = 0;
    Node headdupe = head;
    while (headdupe.next != NULL) {
         headdupe = headdupe.next;
         length++;
    }
    int a = length--;
    for (int y = 0; y < a; y++) {
         head = head.next;
    }
    return head;
}

This is right, but there is also a bonus question that is asking whether we can do the same thing, but only traversing it once. I couldn't think of it during the exam, but after I thought of one way, but I'm not too sure about it.

I could make an ArrayList of length x. Then every time I run the while-loop, I would add an element to the top of the array, cascade down and kick off the last element of the array. Then when the head hits null, return the node at the array[x-1].

Is this right? Is there a better solution?

Answer 1

1. Make 2 pointers to the first node
2. Advance one pointer by x
3. Advance both pointers side by side until the one further in the list hits the end.
4. Your pointer further back points to the xth last element.

Answer 2

You don't need 2 loops which is inefficient, just use 2 pointers and a counter:

Node getNodeFromTail(Node head, int x)
{
    Node p = head;
    Node q = head;

    int diff = 0;

    while (p.next != NULL)
    {
        p = p.next;

        if (diff >= x)
            q = q.next;
        else
            diff++;
    }
    return q;
}

Answer 3

This is the simplest solution

static int getNodeNoStack(ListNode head, int k) {
    ListNode result = head;
    int count = 0;
    while(head.next != null) {
        if(count < k) {
            count++;
        } else {
            result = result.next;
        }
        head = head.next;
    }
    return result.val;
}

You just need to keep the pointer "result" at distance k from head traversing the entire list till the end. Once head is at the end then the result pointer will be at the kth position from tail

Answer 4

You can do it whithout traversing twice or recursion. See the following:

int getNodeFromTail(Node head, int position)
{
    if (head == NULL)
      return 0;

      // 2 pointers needed
      Node first = head;
      Node sec = head;

      for(int i = 0; i < position; i++)
        sec = sec.next;

      while (sec.next != NULL)
      {
        sec = sec.next;
        first = first.next;
      }

      return first;
}

Answer 5

Maintain 2 pointers, Advance First pointer to Nth Node from start Now Point Second Pointer to Head Keep Advancing Both pointers now till first reaches end Second pointer now points to Nth from last

Extra Care in case list has less than N elements

Answer 6

I would do the following:

Keep a circular buffer of size x and add the nodes to it as you traverse the list. When you reach the end of the list, the x'th one from the tail is equal to the next entry in the circular buffer.

In pseudocode:

Node getNodeFromTail(Node head, int x) {
  // Circular buffer with current index of of iteration.
  int[] buffer = new int[x];
  int i = 0;

  do {
    // Place the current head in its position in the buffer and increment
    // the head and the index, continuing if necessary.
    buffer[i++ % x] = head;
    head = head.next;
  } while (head.next != NULL);

  // If we haven't reached x nodes, return NULL, otherwise the next item in the
  // circular buffer holds the item from x heads ago.
  return (i < x) ? NULL : buffer[++i % x];
}

This solution requires an additional x in memory and is a classic example of trading runtime time for memory.

Note: what to do if the input list is smaller than x is undefined.