Question:
Finding the middle element or kth Node of a singly linked list in Java?

Summary: 

This code manages a singly linked list by inserting at the end, computing length, and retrieving nodes. It also converts linked lists to strings for visualization.


Solution:

public class Practice {


  public static void main(String args[]) {

    SinglyLinkedList list = new SinglyLinkedList();

    list.append("1");

    list.append("2");

    list.append("3");

    list.append("4");


    System.out.println("linked list : " + list);


    System.out.println("The first node from last: " + list.getLastNode(1));

    System.out.println("The second node from the end: " + list.getLastNode(2));

    System.out.println("The third node from the tail: " + list.getLastNode(3));

  }

}


/**

 * Java Program to implement linked list data structure

 * 

 * @author Javin

 *

 */

class SinglyLinkedList {

  static class Node {

    private Node next;

    private String data;


    public Node(String data) {

      this.data = data;

    }


    @Override

    public String toString() {

      return data.toString();

    }

  }


  private Node head; // Head is the first node in linked list


  /**

   * checks if linked list is empty

   * 

   * @return true if linked list is empty i.e. no node

   */

  public boolean isEmpty() {

    return length() == 0;

  }


  /**

   * appends a node at the tail of this linked list

   * 

   * @param data

   */

  public void append(String data) {

    if (head == null) {

      head = new Node(data);

      return;

    }

    tail().next = new Node(data);

  }


  /**

   * returns the last node or tail of this linked list

   * 

   * @return last node

   */

  private Node tail() {

    Node tail = head;

    // Find last element of linked list known as tail

    while (tail.next != null) {

      tail = tail.next;

    }

    return tail;

  }


  /**

   * method to get the length of linked list

   * 

   * @return length i.e. number of nodes in linked list

   */

  public int length() {

    int length = 0;

    Node current = head;


    while (current != null) {

      length++;

      current = current.next;

    }

    return length;

  }


  /**

   * to get the nth node from end

   * 

   * @param n

   * @return nth node from last

   */

  public String getLastNode(int n) {

    Node fast = head;

    Node slow = head;

    int start = 1;


    while (fast.next != null) {

      fast = fast.next;

      start++;


      if (start > n) {

        slow = slow.next;

      }

    }


    return slow.data;

  }


  @Override

  public String toString() {

    StringBuilder sb = new StringBuilder();


    Node current = head;

    while (current != null) {

      sb.append(current).append("-->");

      current = current.next;

    }


    if (sb.length() >= 3) {

      sb.delete(sb.length() - 3, sb.length());


    }

    return sb.toString();

  }


}


Output:

linked list : 1-->2-->3-->4

the first node from last: 4

the second node from the end: 3

the third node from the tail: 2


Explenation:

This code defines a basic singly linked list data structure in Java. Here's a breakdown of the provided methods:


  • isEmpty(): Verifies whether the list's length is zero in order to determine whether the linked list is empty.

  • append(String data): Joins the end of the linked list with a new node that has the supplied data.

  • tail(): Gives back the linked list's final node, or tail. 

  • length(): Computes and returns the length of the linked list, i.e., the number of nodes it contains.

  • getLastNode(int n): Retrieves the nth node from the end of the linked list.

  • toString(): Generates a string representation of the linked list, displaying its nodes in sequence.


Credit: >Javarevisited


Suggested blogs:

>Step by Step guide to Deploy Terraform in Azure using GitHub Actions

>Testing react components using Hooks and Mocks

>How to mock a constant value in Python?

>Creating a pivot table by 6 month interval rather than year

>How to do PHP Decryption from Node.js Encryption

>How to Set up the Android emulator?

>How to Set up the local environment for Angular development?

>How to solve encoding issue when writing to a text file, with Python?

>Use Firebase Realtime Database with ASP.NET MVC App

>How to Install mariaDB client efficiently inside docker?

>Can I call an API to find out the random seed in Python `hash()` function?

>How remove residual lines after merge two regions using Geopandas in python?

>How to configure python in jmeter?


Submit
0 Answers
Top Questions
05-02-2024

How to check whether a string is Panagram or not using Java

30-01-2024

How to detect whether the linked list has a loop using Java

14-02-2024

How to check whether all leaves are at the same level using Java

01-02-2024

How to determine the number of valid groupings for a string using Java

15-02-2024

How to Detect cycle in an undirected graph with Java?

Related Questions

Finding all possible permutations of a given string using Java
img
How to check whether all leaves are at the same level using Java
img
How to detect whether the linked list has a loop using Java
img
How to check whether a string is Panagram or not using Java
img
How to clone an undirected graph using Java
img

What Our Clients Say About Us

Client satisfaction is our ultimate goal. Here are some kind words of our precious clients they have used to express their satisfaction with our service.

Why Choose Us ?

We endow businesses with flexible engagement models based on their unique needs. Our strength lies in state-of-the-art technology and affordable consulting services. Try us for fast POCs, full-fledged applications, or technology consulting. Always available for your service.