Insert Node at end of Linked List

Problem Statement: For a given Singly LinkedList, insert a node at the End of the linked list.

Examples:

Example 1:
Input: List = 10->20->30->40->null, Node = 50
Output: 10->20->30->40->50->null
Explanation: Inserted the given node at the end of the linked list.

Example 2:
Input: List = 100->200->300->null, Node =700
Output: 100->200->300->700->null
Explanation: Inserted the given node at the end of the linked list.

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach:

Inserting a Node at the End of LinkedList is 3 step Process

Step 1: Create a node with a value that is to be inserted at end of LinkedList

Step 2: Make the next of Tail Node in LinkedList point to the newly created Node.

Step 3: As the newly created Node is inserted at end of LinkedList, this is the last Node in LinkedList so make a Tail point to the newly inserted Node.

Visual representation of 3 step process for inserting a node at end of LinkedList

Code:

C++ Code

#include <bits/stdc++.h>
using namespace std;

class ListNode {
  public:
       int val;
        ListNode * next;
  ListNode(int x) {
        val = x;
         next = nullptr;
     }
};

ListNode * head, * tail;  // head and tail of the LinkedList

void PrintList()               // Function to print the LinkedList
{
        ListNode * curr = head;
        for (; curr != nullptr; curr = curr -> next)
                cout << curr -> val << "-->";
         cout << "null" << endl;
}

void InsertatLast(int value) {
  // Step1 : creating a new Node with the given val
  ListNode * newnode = new ListNode(value);

  // If head is null, there are no nodes in LinkedList.
  // So the head and tail will be the newly created Node itself.
  if (head == nullptr)
    head = newnode, tail = newnode;

  else {

    // Step2 : Making tail's next point to newly created Node
    tail -> next = newnode;

    // Making newly inserted Node as tail
    tail = newnode;
     }
}

int main() {
  InsertatLast(10);
  InsertatLast(20);
  InsertatLast(30);
  InsertatLast(40);
  cout << "LinkedList before inserting 50 at End : " << endl;
  PrintList();
  InsertatLast(50);
  cout << "LinkedList after inserting 50 at End : " << endl;
  PrintList();
  return 0;
}

Output:

LinkedList before inserting 50 at End :
10–>20–>30–>40–>null
LinkedList after inserting 50 at End :
10–>20–>30–>40–>50–>null

Time Complexity:  O(1) Because we are just Manipulating the links, which is a constant operation.

Space Complexity: O(1) We are not using any extra Space.

Java Code

import java.util.*;

class ListNode {
  int val;
  ListNode next;
  ListNode(int x) {
    val = x;
    next = null;
  }
}
class TUF {

  static ListNode head, tail; // head and tail of the LinkedList

  static void PrintList() // Function to print the LinkedList
  {
    ListNode curr = head;
    for (; curr != null; curr = curr.next)
      System.out.print(curr.val + "-->");
    System.out.println("null");
  }

  static void InsertatLast(int value) {
    // Step1 : creating a new Node with the given val
    ListNode newnode = new ListNode(value);

    // If head is null, there are no nodes in LinkedList.
    // So the head and tail will be the newly created Node itself.
    if (head == null) {
      head = newnode;
      tail = newnode;
    } else {

      // Step2 : Making tail's next point to newly created Node
      tail.next = newnode;

      // Making newly inserted Node as tail
      tail = newnode;
    }
  }

  public static void main(String args[]) {
    InsertatLast(10);
    InsertatLast(20);
    InsertatLast(30);
    InsertatLast(40);
    System.out.println("LinkedList before inserting 50 at End : ");
    PrintList();
    InsertatLast(50);
    System.out.println("LinkedList after inserting 50 at End : ");
    PrintList();
  }
}

Output:

LinkedList before inserting 50 at End :
10–>20–>30–>40–>null
LinkedList after inserting 50 at End :
10–>20–>30–>40–>50–>null

Time Complexity:  O(1) Because we are just Manipulating the links, which is a constant operation.

Space Complexity: O(1) We are not using any extra space.

Special thanks to SaiSri Angajala for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article