Problem Statement: For a given Singly LinkedList, insert a node at the beginning of the linked list.
Examples:
Example 1: Input: List = 10->20->30->40->null, Node = 0 Output: 0->10->20->30->40->null Explanation: Inserted the given node at the beginning of the linked list. Example 2: Input: List = 100->200->300->null, Node =700 Output: 700->100->200->300->null Explanation: Inserted the given node at the beginning of the linked list.
Solution:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Approach:
Inserting a Node at the beginning of LinkedList is 3 step Process
Step 1: First create a node with a value that is to be inserted at the beginning of LinkedList.
Step 2: Point the next of the newly created Node to the head of the LinkedList.
Step 3: As the node is inserted at the beginning of LinkedList, this is the first Node in LinkedList. So point the head of the LinkedList to the newly created Node.
Visual Representation of the 3 Steps involved in inserting a Node at beginning 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 = NULL;
}
};
void PrintList(ListNode * head) // Function to print the LinkedList
{
ListNode * curr = head;
for (; curr != NULL; curr = curr -> next)
cout << curr -> val << "-->";
cout << "null" << endl;
}
ListNode * InsertatFirst(int value, ListNode * head) {
// Step1 : creating a new Node with the given val
ListNode * newnode = new ListNode(value);
// Step2 : Making next of newly created Node to point the head of LinkedList
newnode -> next = head;
// Making the newly created Node as head
head = newnode;
return head;
}
int main() {
ListNode * head = NULL; // head of the LinkedList
head = InsertatFirst(40, head);
head = InsertatFirst(30, head);
head = InsertatFirst(20, head);
head = InsertatFirst(10, head);
cout << "LinkedList before inserting 0 at beginning : " << endl;
PrintList(head);
head = InsertatFirst(0, head);
cout << "LinkedList after inserting 0 at beginning : " << endl;
PrintList(head);
return 0;
}
Output:
LinkedList before inserting 0 at beginning :
10–>20–>30–>40–>null
LinkedList after inserting 0 at beginning :
0–>10–>20–>30–>40–>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 void PrintList(ListNode head) // Function to print the LinkedList
{
ListNode curr = head;
for (; curr != null; curr = curr.next)
System.out.print(curr.val + "-->");
System.out.println("null");
}
static ListNode InsertatFirst(int value, ListNode head) {
// Step1 : creating a new Node with the given val
ListNode newnode = new ListNode(value);
// Step2 : Making next of newly created Node to point the head of LinkedList
newnode.next = head;
// Making the newly created Node as head
head = newnode;
return head;
}
public static void main(String args[]) {
ListNode head = null; // head of the LinkedList
head = InsertatFirst(40, head);
head = InsertatFirst(30, head);
head = InsertatFirst(20, head);
head = InsertatFirst(10, head);
System.out.println("LinkedList before inserting 0 at beginning : ");
PrintList(head);
head = InsertatFirst(0, head);
System.out.println("LinkedList after inserting 0 at beginning : ");
PrintList(head);
}
}
Output:
LinkedList before inserting 0 at beginning :
10–>20–>30–>40–>null
LinkedList after inserting 0 at beginning :
0–>10–>20–>30–>40–>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