C Exercises: Insert a new node at the end of a Singly Linked List
Last update on December 20 2021 09:10:20 [UTC/GMT +8 hours]Required knowledge
Basic C programming, Functions, Singly Linked List, Dynamic memory allocation
Algorithm to insert node at the end of Singly linked list
Algorithm to insert node at the end of a Singly Linked List Begin: createSinglyLinkedList [head] alloc [newNode] If [newNode == NULL] then write ['Unable to allocate memory'] End if Else then read [data] newNode.data ← data newNode.next ← NULL temp ← head While [temp.next != NULL] do temp ← temp.next End while temp.next ← newNode End else End
inserting a node at the end of a linked list
The new node will be added at the end of the linked list.
Linked List | Set 2 [Inserting a node]
We have introduced Linked Lists in the previous post. We also created a simple linked list with 3 nodes and discussed linked list traversal.
All programs discussed in this post consider the following representations of linked list.
C++
|
// A linked list node class Node { public: int data; Node *next; }; // This code is contributed by rathbhupendra |
C
|
// A linked list node struct Node { int data; struct Node *next; }; |
Java
|
// Linked List Class class LinkedList { Node head; // head of list /* Node Class */ class Node { int data; Node next;
// Constructor to create a new node Node[int d] {data = d; next = null; } } } |
Python
|
# Node class class Node: # Function to initialize the node object def __init__[self, data]: self.data = data # Assign data self.next = None # Initialize next as null # Linked List class class LinkedList:
# Function to initialize the Linked List object def __init__[self]: self.head = None |
C#
|
/* Linked list Node*/ public class Node { public int data; public Node next; public Node[int d] {data = d; next = null; } } |
Javascript
|
// Linked List Class var head; // head of list /* Node Class */ class Node { // Constructor to create a new node constructor[d] { this.data = d; this.next = null; } } // This code is contributed by todaysgaurav |
In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways
1] At the front of the linked list
2] After a given node.
3] At the end of the linked list.
Append the last M nodes to the beginning of the given linked list.
Given a linked list and an integer M, the task is to append the last M nodes of the linked list to the front.
Examples:
Input: List = 4 -> 5 -> 6 -> 1 -> 2 -> 3 -> NULL, M = 3
Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
Input: List = 8 -> 7 -> 0 -> 4 -> 1 -> NULL, M = 2
Output: 4 -> 1 -> 8 -> 7 -> 0 -> NULL
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach: Find the first node of the last M nodes in the list, this node will be the new head node so make the next pointer of the previous node as NULL and point the last node of the original list to the head of the original list. Finally, print the updated list.
Below is the implementation of the above approach:
C++
|
// C++ implementation of the approach #include using namespace std; // Class for a node of // the linked list struct Node { // Data and the pointer // to the next node int data; Node* next; Node[int data] { this->data = data; this->next = NULL; } }; // Function to print the linked list void printList[Node* node] { while [node != NULL] { cout data] next; } cout next]]; } // Function to update and print // the updated list nodes void updateList[Node* head, int m] { // Total nodes in the list int cnt = cntNodes[head]; if [cnt != m && m < cnt] { // Count of nodes to be skipped // from the beginning int skip = cnt - m; Node* prev = NULL; Node* curr = head; // Skip the nodes while [skip > 0] { prev = curr; curr = curr->next; skip--; } // Change the pointers prev->next = NULL; Node* tempHead = head; head = curr; // Find the last node while [curr->next != NULL] curr = curr->next; // Connect it to the head // of the sub list curr->next = tempHead; } // Print the updated list printList[head]; } // Driver code int main[] { // Create the list Node* head = new Node[4]; head->next = new Node[5]; head->next->next = new Node[6]; head->next->next->next = new Node[1]; head->next->next->next->next = new Node[2]; head->next->next->next->next->next = new Node[3]; int m = 3; updateList[head, m]; return 0; } // This code is contributed by rutvik_56 |
Java
|
// Java implementation of the approach class GFG { // Class for a node of // the linked list static class Node { // Data and the pointer // to the next node int data; Node next; Node[int data] { this.data = data; this.next = null; } } // Function to print the linked list static void printList[Node node] { while [node != null] { System.out.print[node.data + " -> "]; node = node.next; } System.out.print["NULL"]; } // Recursive function to return the // count of nodes in the linked list static int cntNodes[Node node] { if [node == null] return 0; return [1 + cntNodes[node.next]]; } // Function to update and print // the updated list nodes static void updateList[Node head, int m] { // Total nodes in the list int cnt = cntNodes[head]; if [cnt != m && m < cnt] { // Count of nodes to be skipped // from the beginning int skip = cnt - m; Node prev = null; Node curr = head; // Skip the nodes while [skip > 0] { prev = curr; curr = curr.next; skip--; } // Change the pointers prev.next = null; Node tempHead = head; head = curr; // Find the last node while [curr.next != null] curr = curr.next; // Connect it to the head // of the sub list curr.next = tempHead; } // Print the updated list printList[head]; } // Driver code public static void main[String[] args] { // Create the list Node head = new Node[4]; head.next = new Node[5]; head.next.next = new Node[6]; head.next.next.next = new Node[1]; head.next.next.next.next = new Node[2]; head.next.next.next.next.next = new Node[3]; int m = 3; updateList[head, m]; } } |
Python3
|
# Python3 implementation of the approach # Class for a node of # the linked list class newNode: # Constructor to initialize the node object def __init__[self, data]: self.data = data self.next = None # Function to print the linked list def printList[node]: while [node != None]: print[node.data, "->", end=" "] node = node.next print["NULL"] # Recursive function to return the # count of nodes in the linked list def cntNodes[node]: if [node == None]: return 0 return [1 + cntNodes[node.next]] # Function to update and print # the updated list nodes def updateList[head, m]: # Total nodes in the list cnt = cntNodes[head] if [cnt != m and m < cnt]: # Count of nodes to be skipped # from the beginning skip = cnt - m prev = None curr = head # Skip the nodes while [skip > 0]: prev = curr curr = curr.next skip -= 1 # Change the pointers prev.next = None tempHead = head head = curr # Find the last node while [curr.next != None]: curr = curr.next # Connect it to the head # of the sub list curr.next = tempHead # Print the updated list printList[head] # Driver code # Create the list head = newNode[4] head.next = newNode[5] head.next.next = newNode[6] head.next.next.next = newNode[1] head.next.next.next.next = newNode[2] head.next.next.next.next.next = newNode[3] m = 3 updateList[head, m] # This code is contributed by shubhamsingh20 |
C#
|
// C# implementation of the approach using System; class GFG { // Class for a node of // the linked list class Node { // Data and the pointer // to the next node public int data; public Node next; public Node[int data] { this.data = data; this.next = null; } } // Function to print the linked list static void printList[Node node] { while [node != null] { Console.Write[node.data + " -> "]; node = node.next; } Console.Write["NULL"]; } // Recursive function to return the // count of nodes in the linked list static int cntNodes[Node node] { if [node == null] return 0; return [1 + cntNodes[node.next]]; } // Function to update and print // the updated list nodes static void updateList[Node head, int m] { // Total nodes in the list int cnt = cntNodes[head]; if [cnt != m && m < cnt] { // Count of nodes to be skipped // from the beginning int skip = cnt - m; Node prev = null; Node curr = head; // Skip the nodes while [skip > 0] { prev = curr; curr = curr.next; skip--; } // Change the pointers prev.next = null; Node tempHead = head; head = curr; // Find the last node while [curr.next != null] curr = curr.next; // Connect it to the head // of the sub list curr.next = tempHead; } // Print the updated list printList[head]; } // Driver code public static void Main[String[] args] { // Create the list Node head = new Node[4]; head.next = new Node[5]; head.next.next = new Node[6]; head.next.next.next = new Node[1]; head.next.next.next.next = new Node[2]; head.next.next.next.next.next = new Node[3]; int m = 3; updateList[head, m]; } } // This code is contributed by PrinciRaj1992 |
Javascript
|
// JavaScript implementation of the approach // Class for a node of // the linked list class Node { // Data and the pointer // to the next node constructor[data] { this.data = data; this.next = null; } } // Function to print the linked list function printList[node] { while [node != null] { document.write[node.data + " -> "]; node = node.next; } document.write["NULL"]; } // Recursive function to return the // count of nodes in the linked list function cntNodes[node] { if [node == null] return 0; return 1 + cntNodes[node.next]; } // Function to update and print // the updated list nodes function updateList[head, m] { // Total nodes in the list var cnt = cntNodes[head]; if [cnt != m && m < cnt] { // Count of nodes to be skipped // from the beginning var skip = cnt - m; var prev = null; var curr = head; // Skip the nodes while [skip > 0] { prev = curr; curr = curr.next; skip--; } // Change the pointers prev.next = null; var tempHead = head; head = curr; // Find the last node while [curr.next != null] curr = curr.next; // Connect it to the head // of the sub list curr.next = tempHead; } // Print the updated list printList[head]; } // Driver code // Create the list var head = new Node[4]; head.next = new Node[5]; head.next.next = new Node[6]; head.next.next.next = new Node[1]; head.next.next.next.next = new Node[2]; head.next.next.next.next.next = new Node[3]; var m = 3; updateList[head, m];
// This code is contributed by rdtank.
|
Output
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
METHOD 2:
We Will use modififcation of runner’s technique :-
1. find the kth node from end using runner technique and do the following modifications
2. now we have to update our pointers as
a] fast->next will be pointing to head,
b]slow->next will be new head,
c]last node will be the slow->next hence it should point to null
C++
|
#include using namespace std; struct node { int data; node* next; node[int x] { data = x; next = NULL; } }; void insertAtTail[node*& head, int x] { if [head == NULL] { head = new node[x]; return; } node* curr = head; while [curr->next != NULL] { curr = curr->next; } node* t = new node[x]; curr->next = t; } void print[node* head] { node* curr = head; while [curr != NULL] { cout data next; } cout next; } while [fast->next != NULL] { slow = slow->next; fast = fast->next; } // cout2 --->3 with node structure as below: struct node { int data; struct node *next; };Video liên quanChủ Đề |