What is the time complexity of setting the value of the nth element in a singly linked list?

Improve Article

Save Article

Like Article

Given a Linked List and a number N, write a function that returns the value at the Nth node from the end of the Linked List.

Linked-List

Examples:

Input: 1 -> 2 -> 3 -> 4, N = 3
Output: 2
Input: 35 -> 15 -> 4 -> 20, N = 4
Output: 35

Naive Approach: Follow the given steps to solve the problem using this approach:

Calculate the length of the Linked List. Let the length be len.
Print the (len – n + 1)th node from the beginning of the Linked List.

Below is the implementation of the above approach:

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node* next;
} Node;
void printNthFromLast(Node* head, int N)
{
    int len = 0, i;
    Node* temp = head;
    while (temp != NULL) {
        temp = temp->next;
        len++;
    }
    if (len < N)
        return;
    temp = head;
    for (i = 1; i < len - N + 1; i++)
        temp = temp->next;
    printf("%d", temp->data);
    return;
}
void push(struct Node** head_ref, int new_data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
int main()
{
    struct Node* head = NULL;
    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 35);
    printNthFromLast(head, 4);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void printNthFromLast(struct Node* head, int N)
{
    int len = 0, i;
    struct Node* temp = head;
    while (temp != NULL) {
        temp = temp->next;
        len++;
    }
    if (len < N)
        return;
    temp = head;
    for (i = 1; i < len - N + 1; i++)
        temp = temp->next;
    cout << temp->data;
    return;
}
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
int main()
{
    struct Node* head = NULL;
    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 35);
    printNthFromLast(head, 4);
    return 0;
}

class LinkedList {
    Node head; 
    class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
    void printNthFromLast(int N)
    {
        int len = 0;
        Node temp = head;
        while (temp != null) {
            temp = temp.next;
            len++;
        }
        if (len < N)
            return;
        temp = head;
        for (int i = 1; i < len - N + 1; i++)
            temp = temp.next;
        System.out.println(temp.data);
    }
    public void push(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }



    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(35);
        llist.printNthFromLast(4);
    }
} 

class Node:
    def __init__(self, new_data):
        self.data = new_data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
    def printNthFromLast(self, n):
        temp = self.head  
        length = 0
        while temp is not None:
            temp = temp.next
            length += 1
        if n > length:  
            print('Location is greater than the' +
                  ' length of LinkedList')
            return
        temp = self.head
        for i in range(0, length - n):
            temp = temp.next
        print(temp.data)
if __name__ == "__main__":
    llist = LinkedList()
    llist.push(20)
    llist.push(4)
    llist.push(15)
    llist.push(35)
    llist.printNthFromLast(4)

using System;
public class LinkedList {
    public Node head; 
    public class Node {
        public int data;
        public Node next;
        public Node(int d)
        {
            data = d;
            next = null;
        }
    }
    void printNthFromLast(int N)
    {
        int len = 0;
        Node temp = head;
        while (temp != null) {
            temp = temp.next;
            len++;
        }
        if (len < N)
            return;
        temp = head;
        for (int i = 1; i < len - N + 1; i++)
            temp = temp.next;
        Console.WriteLine(temp.data);
    }
    public void push(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
    public static void Main(String[] args)
    {
        LinkedList llist = new LinkedList();
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(35);
        llist.printNthFromLast(4);
    }
}

  class Node {
      constructor(d)
      {
          this.data = d;
          this.next = null;
      }
  }
  class LinkedList
  {
    constructor(d){
      this.head = d;
    }
  printNthFromLast(n)
  {
      let len = 0;
      let temp = this.head;
      while (temp != null) {
          temp = temp.next;
          len++;
      }
      if (len < n)
          return;
      temp = this.head;
      for (let i = 1; i < len - n + 1; i++)
          temp = temp.next;
      document.write(temp.data);
  }
  push(new_data)
  {
      let new_node = new Node(new_data);
      new_node.next = this.head;
      this.head = new_node;
  }
  }
      let llist = new LinkedList();



      llist.push(20);
      llist.push(4);
      llist.push(15);
      llist.push(35);
      llist.printNthFromLast(4);

Time complexity: O(M) where M is the size of the linked list
Auxiliary Space: O(1)

Below is a recursive code for the same method. Thanks to Anuj Bansal for providing the following code.

void printNthFromLast(struct Node* head, int N)
{
    static int i = 0;
    if (head == NULL)
        return;
    printNthFromLast(head->next, N);
    if (++i == N)
        printf("%d", head->data);
}

void printNthFromLast(struct Node* head, int N)
{
    static int i = 0;
    if (head == NULL)
        return;
    printNthFromLast(head->next, N);
    if (++i == N)
        cout<<head->data;
}

static void printNthFromLast(Node head, int N)
{
    int i = 0;
    if (head == null)
        return;
    printNthFromLast(head.next, N);
    if (++i == N)
        System.out.print(head.data);
}

def printNthFromLast(head, N):
    i = 0
    if (head == None)
        return
    printNthFromLast(head.next, N);
    i += 1
    if (i == N):
        print(head.data)

static void printNthFromLast(Node head, int N)
{
    static int i = 0;
    if (head == null)
        return;
    printNthFromLast(head.next, N);
    if (++i == N)
        Console.Write(head.data);
}

function printNthFromLast(head , N)
{
    function i = 0;
    if (head == null)
        return;
    printNthFromLast(head.next, N);
    if (++i == N)
        document.write(head.data);
}

Time Complexity: O(M) where M is the length of the linked list.
Auxiliary Space: O(M) for call stack

Nth node from the end of a Linked List using two pointers:

As Nth node from the end equals to (Length – N + 1)th node from the start, so the idea is to Maintain two pointers starting from the head of the Linked-List and move one pointer to the Nth node from the start and then move both the pointers together until the pointer at the Nth position reaches the last node. Now the pointer which was moved later points at the Nth node from the end of the Linked-List

Below image is a dry run of the above approach:

Follow the given steps to solve the problem:

Maintain two pointers main_ptr and ref_ptr
Move ref_ptr to the Nth node from the start
Now move both main_ptr and ref_ptr, until the ref_ptr reaches the last node
Now print the data of the main_ptr, as it is at the Nth node from the end

Below is the implementation of the above approach:

#include <bits/stdc++.h>
using namespace std;
struct node {
    int data;
    node* next;
    node(int val)
    {
        data = val;
        next = NULL;
    }
};
struct llist {
    node* head;
    llist() { head = NULL; }
    void insertAtBegin(int val)
    {
        node* newNode = new node(val);
        newNode->next = head;
        head = newNode;
    }
    void nthFromEnd(int n)
    {
        node* main_ptr = head;
        node* ref_ptr = head;
        if (head == NULL) {
            cout << "List is empty" << endl;
            return;
        }
        for (int i = 1; i < n; i++) {
            ref_ptr = ref_ptr->next;
            if (ref_ptr == NULL) {
                cout << n



                     << " is greater than no. of nodes in "
                        "the list"
                     << endl;
                return;
            }
        }
        while (ref_ptr != NULL && ref_ptr->next != NULL) {
            ref_ptr = ref_ptr->next;
            main_ptr = main_ptr->next;
        }
        cout << "Node no. " << n
             << " from end is: " << main_ptr->data << endl;
    }
    void displaylist()
    {
        node* temp = head;
        while (temp != NULL) {
            cout << temp->data << "->";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }
};
int main()
{
    llist ll;
    ll.insertAtBegin(20);
    ll.insertAtBegin(4);
    ll.insertAtBegin(15);
    ll.insertAtBegin(35);
    ll.displaylist();
    ll.nthFromEnd(4);
    return 0;
}

class LinkedList {
    Node head; 
    class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
    void printNthFromLast(int N)
    {
        Node main_ptr = head;
        Node ref_ptr = head;
        int count = 0;
        if (head != null) {
            while (count < N) {
                if (ref_ptr == null) {
                    System.out.println(
                        N + " is greater than the no "
                        + " of nodes in the list");
                    return;
                }
                ref_ptr = ref_ptr.next;
                count++;
            }
            if (ref_ptr == null) {
                if (head != null)
                    System.out.println("Node no. " + N
                                       + " from last is "
                                       + head.data);
            }
            else {
                while (ref_ptr != null) {
                    main_ptr = main_ptr.next;
                    ref_ptr = ref_ptr.next;
                }
                System.out.println("Node no. " + N
                                   + " from last is "
                                   + main_ptr.data);
            }
        }
    }
    public void push(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(35);
        llist.printNthFromLast(4);
    }
}

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
    def printNthFromLast(self, N):
        main_ptr = self.head
        ref_ptr = self.head
        count = 0
        if(self.head is not None):
            while(count < N):
                if(ref_ptr is None):
                    print("% d is greater than the no. pf nodes in list" % (N))
                    return
                ref_ptr = ref_ptr.next
                count += 1
        if(ref_ptr is None):
            self.head = self.head.next
            if(self.head is not None):
                print("Node no. % d from last is % d "
                      % (N, main_ptr.data))
        else:
            while(ref_ptr is not None):
                main_ptr = main_ptr.next
                ref_ptr = ref_ptr.next



            print("Node no. % d from last is % d "
                  % (N, main_ptr.data))
if __name__ == '__main__':
    llist = LinkedList()
    llist.push(20)
    llist.push(4)
    llist.push(15)
    llist.push(35)
    llist.printNthFromLast(4)

using System;
public class LinkedList {
    Node head; 
    public class Node {
        public int data;
        public Node next;
        public Node(int d)
        {
            data = d;
            next = null;
        }
    }
    void printNthFromLast(int N)
    {
        Node main_ptr = head;
        Node ref_ptr = head;
        int count = 0;
        if (head != null) {
            while (count < N) {
                if (ref_ptr == null) {
                    Console.WriteLine(
                        N + " is greater than the no "
                        + " of nodes in the list");
                    return;
                }
                ref_ptr = ref_ptr.next;
                count++;
            }
            if (ref_ptr == null) {
                head = head.next;
                if (head != null)
                    Console.WriteLine("Node no. " + N
                                      + " from last is "
                                      + main_ptr.data);
            }
            else {
                while (ref_ptr != null) {
                    main_ptr = main_ptr.next;
                    ref_ptr = ref_ptr.next;
                }
                Console.WriteLine("Node no. " + N
                                  + " from last is "
                                  + main_ptr.data);
            }
        }
    }
    public void push(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
    public static void Main(String[] args)
    {
        LinkedList llist = new LinkedList();
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(35);
        llist.printNthFromLast(4);
    }
}

var head; 
     class Node {
            constructor(val) {
                this.data = val;
                this.next = null;
            }
        }
    function printNthFromLast(n)
    {
        var main_ptr = head;
        var ref_ptr = head;
        var count = 0;
        if (head != null) {
            while (count < n) {
                if (ref_ptr == null) {
                    document.write(n + " is greater than the no " +
                    " of nodes in the list");
                    return;
                }
                ref_ptr = ref_ptr.next;
                count++;
            }
            if (ref_ptr == null) {
                if (head != null)
                    document.write("Node no. " + n + " from last is " + head.data);
            } else {
                while (ref_ptr != null) {
                    main_ptr = main_ptr.next;
                    ref_ptr = ref_ptr.next;
                }
                document.write("Node no. " + n + " from last is " + main_ptr.data);
            }
        }
    }
     function push(new_data) {
        var new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
        push(20);
        push(4);
        push(15);
        push(35);
        printNthFromLast(4);