Monday, March 5, 2018

Program to find the Nth Element of a Singly Linked list from the end in java

Data structure is one of the most asked interview topic for java developer interviews and believe me linked list is one of the most favorite area of data structure , there are so many other interview questions for linked list and one of them we will discuss today in this post.





Objective - To Find the Nth Element of a Given Singly Linked list from the End.

First we will see the Psuedo code (simple logic of solving the problem ) and then will look for the java implementation.

Psuedo Code :(nth element from the end )
  • We first initialize 2 pointer both heading to the first element let say left and right
  • We then move the right pointer to n(where n is the count of the number from the end ) times toward the right side.
  • Now we will start moving both the pointer to the right side one by one till  right pointer reaches to the last element keping the left pointer fixed.
  • At this point the Element left pointer pointing is the required element.



Implementation



public class Nth {
    public static void main(String[] args) {
        // NOTE: The following input values will be used for testing your solution.
        Node current = new Node(1, null);
        for (int i = 2; i < 8; i++) {
            current = new Node(i, current);
        }
        Node head = current;
        // head = 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> (null)

        Node current2 = new Node(4, null);
        for (int i = 3; i > 0; i--) {
            current2 = new Node(i, current2);
        }
        Node head2 = current2;
        // head2 = 1 -> 2 -> 3 -> 4 -> (null)

        // nthFromLast(head, 1) should return 1.
        // nthFromLast(head, 5) should return 5.
        // nthFromLast(head2, 2) should return 3.
        // nthFromLast(head2, 4) should return 1.
        // nthFromLast(head2, 5) should return null.
        // nthFromLast(null, 1) should return null.
    }


    // Implement your function below.
    public static Node nthFromLast(Node head, int n) {
        Node left = head;
        Node right = head;

        // First, make sure that we have at least n items in the linked list.
        for (int i = 0; i < n; i++) {
            if (right == null) return null;
            right = right.child;
        }
        while (right != null) {
            right = right.child;
            left = left.child;
        }
        return left;
    }


    //  NOTE: Feel free to use the following function for testing.
    //  It converts the given linked list into an easy-to-read string format.
    //  Example: 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> (null)
    public static String linkedListToString(Node head) {
        Node current = head;
        StringBuilder sb = new StringBuilder();
        while (current != null) {
            sb.append(String.valueOf(current.value));
            sb.append(" -> ");
            current = current.child;
        }
        sb.append("(null)");
        return sb.toString();
    }
 }


public class Node {
 
 int data;
 Node child;
 
 Node(){}
 
 public Node(int data , Node child) {
  this.data=data;
  this.child=child;
 }

}


If you like this article do share with your friends and colleagues. and if have any query leave us a comment.

Happy Learning

Thanks for reading
Noeik

0 comments:

Post a Comment