Merge two sorted Linked Lists

Here we will write a function merge(list 1, list 2) which will take two sorted linked list as argument and it will merge them to form a new linked list in ascending order.

For example we will have two linked lists 2 -> 5 -> 9 and  3 -> 7 -> 11 and the function will create third linked list as 2 -> 3 -> 5 -> 7 -> 9 -> 11.

Let’s see the code.

Program to Merge two sorted Linked Lists in C++

 

Sample Output:

Write a Program to reverse a Linked list

There are many ways to reverse a linked list, but here we’ll discuss 2 methods to do so.

1.  Iterative Method:

This is the most simple method to reverse a linked list. This is the first thought that would come to anybody’s mind if he/she thinks on how to reverse a linked list. Let’s take a simple linked list:

reverse a linked list

 

Now what we are gonna do is to make the last node as head and first as tail, so simply we will reverse the links in opposite direction and make head as last member of linked list, so that the linked list becomes reverse.

Technically: Iterate through the linked list. In loop, change next to prev, prev to current and current to next.

Now let’s implement this in program:

Reverse a Linked List using Iterative method:

Sample Output:

Time Complexity: O(n)
Space Complexity: O(1)

 

2.  Using Recursion:

  • Divide the list in two parts – first node and rest of the linked list.
  • Call reverse for the rest of the linked list.
  • Link rest to first.
  • Fix head pointer

reverse a linked list

 

Reverse a linked list using recursion:

Time Complexity: O(n)
Space Complexity: O(1)

Just use this function in the same program and you will get the output.

For any query comment below.

Program to implement Queue using Linked List C++

Today we are going to write a program to implement queue using linked list C++, let’s start with what is queue:

 

What is QUEUE?

implement queue using linked list C++

 

 

A Queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure.

 

Program to implement Queue using Linked List C++

 

OUTPUT:

 

C++ program to implement Stack using Linked List

In this post we will write a program to implement Stack using Linked List. Let’s first understand what is Stack:

Stack:

A stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed. The order in which elements come off a stack gives rise to its alternative name, LIFO (for last in, first out).

Below image will make it clear:

stack using linked list

There are two ways to implement Stack in C C++

  1. Using Array
  2. Using Linked List

Here I’ve Discussed how to implement Stack using Linked List.

 

C++ Program to implement Stack using Linked List:

 

 

OUTPUT:

Program to implement Stack using Arrays in C C++

In this post we will write a program to implement Stack using Arrays. Let’s first understand what is Stack:

Stack:

A stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed. The order in which elements come off a stack gives rise to its alternative name, LIFO (for last in, first out).

Below image will make it clear:

implement stack using arrays

There are two ways to implement Stacks in C C++

  1. Using Array
  2. Using Linked List

Here I’ve Discussed how to implement Stack using Arrays.

Here is the source code to implement stack in c c++.

Program to implement Stack using Arrays:

 

OUTPUT:

 

Comment if you face any problem.

Program to implement Linked List in C C++

Following is the program to implement linked list in c  c++

PROGRAM: