|
Given a linked list, the task is to insert a new node at the end of the linked list.
Examples:
Input: LinkedList = 2 -> 3 -> 4 -> 5, NewNode = 1
Output: LinkedList = 2 -> 3 -> 4 -> 5 -> 1
Input: LinkedList = NULL, NewNode = 1
Output: LinkedList = 1
Approach:
Inserting at the end involves traversing the entire list until we reach the last node. We then set the last node’s next reference to point to the new node, making the new node the last element in the list.
 Following is the approach to add a new node at the end of the linked list:
- Create a new node and set its next pointer as NULL since it will be the last node.
- Store the head reference in a temporary variable
- If the Linked List is empty, make the new node as the head and return
- Else traverse till the last node
- Change the next pointer of the last node to point to the new node
Below is the implementation of the approach:
C++
#include <iostream>
using namespace std;
// A linked list node
class Node {
public:
int data;
Node* next;
// Constructor to initialize a new node with data
Node(int new_data) {
data = new_data;
next = nullptr;
}
};
// Given the head of a list and an int, appends
// a new node at the end and returns the head.
Node* append(Node* head, int new_data) {
// Create a new node
Node* new_node = new Node(new_data);
// If the Linked List is empty, make
// the new node as the head and return
if (head == nullptr) {
return new_node;
}
// Store the head reference in a temporary variable
Node* last = head;
// Traverse till the last node
while (last->next != nullptr) {
last = last->next;
}
// Change the next pointer of the last node
// to point to the new node
last->next = new_node;
// Return the head of the list
return head;
}
// This function prints the contents
// of the linked list starting from the head
void printList(Node* node) {
while (node != nullptr) {
cout << " " << node->data;
node = node->next;
}
}
// Driver code
int main() {
// Create a hard-coded linked list:
// 2 -> 3 -> 4 -> 5 -> 6
Node* head = new Node(2);
head->next = new Node(3);
head->next->next = new Node(4);
head->next->next->next = new Node(5);
head->next->next->next->next = new Node(6);
cout << "Created Linked list is:";
printList(head);
// Example of appending a node at the end
head = append(head, 1);
cout << "\nAfter inserting 1 at the end:";
printList(head);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
// A linked list node
struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int new_data) {
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}
// Given the head of a list and an int, appends
// a new node at the end and returns the head.
struct Node* append(struct Node* head, int new_data) {
// Create a new node
struct Node* new_node = createNode(new_data);
// If the Linked List is empty, make
// the new node as the head and return
if (head == NULL) {
return new_node;
}
// Store the head reference in a temporary variable
struct Node* last = head;
// Traverse till the last node
while (last->next != NULL) {
last = last->next;
}
// Change the next pointer of the last node
// to point to the new node
last->next = new_node;
// Return the head of the list
return head;
}
// This function prints the contents
// of the linked list starting from the head
void printList(struct Node* node) {
while (node != NULL) {
printf(" %d", node->data);
node = node->next;
}
}
// Driver code
int main() {
// Create a hard-coded linked list:
// 2 -> 3 -> 4 -> 5 -> 6
struct Node* head = createNode(2);
head->next = createNode(3);
head->next->next = createNode(4);
head->next->next->next = createNode(5);
head->next->next->next->next = createNode(6);
printf("Created Linked list is:");
printList(head);
// Example of appending a node at the end
head = append(head, 1);
printf("\nAfter inserting 1 at the end:");
printList(head);
return 0;
}
class Node {
int data;
Node next;
// Constructor to initialize a new node with data
Node(int newData) {
data = newData;
next = null;
}
}
public class GfG {
// Given the head of a list and an int, appends
// a new node at the end and returns the head.
static Node append(Node head, int newData) {
// Create a new node
Node newNode = new Node(newData);
// If the Linked List is empty, make the new
// node as the head and return
if (head == null) {
return newNode;
}
// Store the head reference in a temporary variable
Node last = head;
// Traverse till the last node
while (last.next != null) {
last = last.next;
}
// Change the next pointer of the
// last node to point to the new node
last.next = newNode;
// Return the head of the list
return head;
}
// This function prints the contents of
// the linked list starting from the head
public static void printList(Node node) {
while (node != null) {
System.out.print(" " + node.data);
node = node.next;
}
}
// Driver code
public static void main(String[] args) {
// Create a hard-coded linked list:
// 2 -> 3 -> 4 -> 5 -> 6
Node head = new Node(2);
head.next = new Node(3);
head.next.next = new Node(4);
head.next.next.next = new Node(5);
head.next.next.next.next = new Node(6);
System.out.print("Created Linked list is:");
printList(head);
// Example of appending a node at the end
head = append(head, 1);
System.out.print("\nAfter inserting 1 at the end:");
printList(head);
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Given the head of a list and an int, appends
# a new node at the end and returns the head.
def append(head, new_data):
# Create a new node
new_node = Node(new_data)
# If the Linked List is empty, make the
# new node as the head and return
if head is None:
return new_node
# Store the head reference in a temporary variable
last = head
# Traverse till the last node
while last.next:
last = last.next
# Change the next pointer of the last
# node to point to the new node
last.next = new_node
# Return the head of the list
return head
# This function prints the contents of the
# linked list starting from the head
def print_list(node):
while node:
print(node.data, end=" ")
node = node.next
# Driver code
if __name__ == "__main__":
# Create a hard-coded linked list:
# 2 -> 3 -> 4 -> 5 -> 6
head = Node(2)
head.next = Node(3)
head.next.next = Node(4)
head.next.next.next = Node(5)
head.next.next.next.next = Node(6)
print("Created Linked list is: ", end="")
print_list(head)
# Example of appending a node at the end
head = append(head, 1)
print("\nAfter inserting 1 at the end: ", end="")
print_list(head)
using System;
public class Node
{
public int data;
public Node next;
// Constructor to initialize a new node with data
public Node(int newData)
{
data = newData;
next = null;
}
}
// Appends a new node at the end
// and returns the head.
public class GfG
{
public static Node Append(Node head, int newData)
{
// Create a new node
Node newNode = new Node(newData);
// If the Linked List is empty,
// make the new node as the head
if (head == null)
{
return newNode;
}
// Store the head reference in a
// temporary variable
Node last = head;
// Traverse till the last node
while (last.next != null)
{
last = last.next;
}
// Change the next pointer of the
// last node to point to the new node
last.next = newNode;
// Return the head of the list
return head;
}
// Prints the contents of the linked
// list starting from the head
public static void PrintList(Node node)
{
while (node != null)
{
Console.Write(node.data + " ");
node = node.next;
}
}
// Driver code
public static void Main(string[] args)
{
// Create a hard-coded linked list:
// 2 -> 3 -> 4 -> 5 -> 6
Node head = new Node(2);
head.next = new Node(3);
head.next.next = new Node(4);
head.next.next.next = new Node(5);
head.next.next.next.next = new Node(6);
Console.Write("Created Linked list is: ");
PrintList(head);
// Example of appending a node
// at the end
head = Append(head, 1);
Console.Write("\nAfter inserting 1 at the end: ");
PrintList(head);
}
}
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Appends a new node at the end
// and returns the head.
function append(head, newData) {
// Create a new node
const newNode = new Node(newData);
// If the Linked List is empty,
// make the new node as the head
if (head === null) {
return newNode;
}
// Store the head reference in a
// temporary variable
let last = head;
// Traverse till the last node
while (last.next !== null) {
last = last.next;
}
// Change the next pointer of the
// last node to point to the new node
last.next = newNode;
// Return the head of the list
return head;
}
// Prints the contents of the linked
// list starting from the head
function printList(node) {
while (node !== null) {
console.log(node.data + " ");
node = node.next;
}
}
// Create a hard-coded linked list:
// 2 -> 3 -> 4 -> 5 -> 6
let head = new Node(2);
head.next = new Node(3);
head.next.next = new Node(4);
head.next.next.next = new Node(5);
head.next.next.next.next = new Node(6);
console.log("Created Linked list is:");
printList(head);
// Example of appending a node
// at the end
head = append(head, 1);
console.log("\nAfter inserting 1 at the end:");
printList(head);
OutputCreated Linked list is: 2 3 4 5 6
After inserting 1 at the end: 2 3 4 5 6 1 Time Complexity: O(N) where N is the length of the linked list
Auxiliary Space: O(1)
|
