Continue Traversing Linked List After Finding Match C
Given a linked list which is sorted, how will you insert in sorted way
Given a sorted linked list and a value to insert, write a function to insert the value in a sorted way.
Initial Linked List
Linked List after insertion of 9
Algorithm:
Let input linked list is sorted in increasing order.
1) If Linked list is empty then make the node as head and return it. 2) If the value of the node to be inserted is smaller than the value of the head node, then insert the node at the start and make it head. 3) In a loop, find the appropriate node after which the input node (let 9) is to be inserted. To find the appropriate node start from the head, keep moving until you reach a node GN (10 in the below diagram) who's value is greater than the input node. The node just before GN is the appropriate node (7). 4) Insert the node (9) after the appropriate node (7) found in step 3.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
class Node {
public :
int data;
Node* next;
};
void sortedInsert(Node** head_ref,
Node* new_node)
{
Node* current;
if (*head_ref == NULL
|| (*head_ref)->data
>= new_node->data) {
new_node->next = *head_ref;
*head_ref = new_node;
}
else {
current = *head_ref;
while (current->next != NULL
&& current->next->data
< new_node->data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
Node* newNode( int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}
void printList(Node* head)
{
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " " ;
temp = temp->next;
}
}
int main()
{
Node* head = NULL;
Node* new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(7);
sortedInsert(&head, new_node);
new_node = newNode(3);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
cout << "Created Linked List\n" ;
printList(head);
return 0;
}
C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void sortedInsert( struct Node** head_ref,
struct Node* new_node)
{
struct Node* current;
if (*head_ref == NULL
|| (*head_ref)->data
>= new_node->data) {
new_node->next = *head_ref;
*head_ref = new_node;
}
else {
current = *head_ref;
while (current->next != NULL
&& current->next->data < new_node->data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
struct Node* newNode( 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;
}
void printList( struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf ( "%d " , temp->data);
temp = temp->next;
}
}
int main()
{
struct Node* head = NULL;
struct Node* new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(7);
sortedInsert(&head, new_node);
new_node = newNode(3);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
printf ( "\n Created Linked List\n" );
printList(head);
return 0;
}
Java
class LinkedList {
Node head;
class Node {
int data;
Node next;
Node( int d)
{
data = d;
next = null ;
}
}
void sortedInsert(Node new_node)
{
Node current;
if (head == null || head.data
>= new_node.data) {
new_node.next = head;
head = new_node;
}
else {
current = head;
while (current.next != null
&& current.next.data < new_node.data)
current = current.next;
new_node.next = current.next;
current.next = new_node;
}
}
Node newNode( int data)
{
Node x = new Node(data);
return x;
}
void printList()
{
Node temp = head;
while (temp != null ) {
System.out.print(temp.data + " " );
temp = temp.next;
}
}
public static void main(String args[])
{
LinkedList llist = new LinkedList();
Node new_node;
new_node = llist.newNode( 5 );
llist.sortedInsert(new_node);
new_node = llist.newNode( 10 );
llist.sortedInsert(new_node);
new_node = llist.newNode( 7 );
llist.sortedInsert(new_node);
new_node = llist.newNode( 3 );
llist.sortedInsert(new_node);
new_node = llist.newNode( 1 );
llist.sortedInsert(new_node);
new_node = llist.newNode( 9 );
llist.sortedInsert(new_node);
System.out.println( "Created Linked List" );
llist.printList();
}
}
Python
class Node:
def __init__( self , data):
self .data = data
self . next = None
class LinkedList:
def __init__( self ):
self .head = None
def sortedInsert( self , new_node):
if self .head is None :
new_node. next = self .head
self .head = new_node
elif self .head.data > = new_node.data:
new_node. next = self .head
self .head = new_node
else :
current = self .head
while (current. next is not None and
current. next .data < new_node.data):
current = current. next
new_node. next = current. next
current. next = new_node
def push( self , new_data):
new_node = Node(new_data)
new_node. next = self .head
self .head = new_node
def printList( self ):
temp = self .head
while (temp):
print temp.data,
temp = temp. next
llist = LinkedList()
new_node = Node( 5 )
llist.sortedInsert(new_node)
new_node = Node( 10 )
llist.sortedInsert(new_node)
new_node = Node( 7 )
llist.sortedInsert(new_node)
new_node = Node( 3 )
llist.sortedInsert(new_node)
new_node = Node( 1 )
llist.sortedInsert(new_node)
new_node = Node( 9 )
llist.sortedInsert(new_node)
print "Create Linked List"
llist.printList()
C#
using System;
public class LinkedList {
Node head;
class Node {
public int data;
public Node next;
public Node( int d)
{
data = d;
next = null ;
}
}
void sortedInsert(Node new_node)
{
Node current;
if (head == null || head.data >= new_node.data) {
new_node.next = head;
head = new_node;
}
else {
current = head;
while (current.next != null && current.next.data < new_node.data)
current = current.next;
new_node.next = current.next;
current.next = new_node;
}
}
Node newNode( int data)
{
Node x = new Node(data);
return x;
}
void printList()
{
Node temp = head;
while (temp != null ) {
Console.Write(temp.data + " " );
temp = temp.next;
}
}
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
Node new_node;
new_node = llist.newNode(5);
llist.sortedInsert(new_node);
new_node = llist.newNode(10);
llist.sortedInsert(new_node);
new_node = llist.newNode(7);
llist.sortedInsert(new_node);
new_node = llist.newNode(3);
llist.sortedInsert(new_node);
new_node = llist.newNode(1);
llist.sortedInsert(new_node);
new_node = llist.newNode(9);
llist.sortedInsert(new_node);
Console.WriteLine( "Created Linked List" );
llist.printList();
}
}
Javascript
<script>
var head;
class Node {
constructor(val) {
this .data = val;
this .next = null ;
}
}
function sortedInsert( new_node) {
var current;
if (head == null || head.data >= new_node.data) {
new_node.next = head;
head = new_node;
} else {
current = head;
while (current.next != null && current.next.data < new_node.data)
current = current.next;
new_node.next = current.next;
current.next = new_node;
}
}
function newNode(data) {
x = new Node(data);
return x;
}
function printList() {
temp = head;
while (temp != null ) {
document.write(temp.data + " " );
temp = temp.next;
}
}
var new_node;
new_node = newNode(5);
sortedInsert(new_node);
new_node = newNode(10);
sortedInsert(new_node);
new_node = newNode(7);
sortedInsert(new_node);
new_node = newNode(3);
sortedInsert(new_node);
new_node = newNode(1);
sortedInsert(new_node);
new_node = newNode(9);
sortedInsert(new_node);
document.write( "Created Linked List<br/>" );
printList();
</script>
Output:
Created Linked List 1 3 5 7 9 10
Complexity Analysis:
- Time Complexity: O(n).
Only one traversal of the list is needed. - Auxiliary Space: O(1).
No extra space is needed.
Shorter Implementation using double pointers:
Thanks to Murat M Ozturk for providing this solution. Please see Murat M Ozturk's comment below for complete function. The code uses double-pointer to keep track of the next pointer of the previous node (after which new node is being inserted).
Note that below line in code changes current to have address of next pointer in a node.
current = &((*current)->next);
Also, note below comments.
/* Copies the value-at-address current to new_node's next pointer*/ new_node->next = *current; /* Fix next pointer of the node (using its address) after which new_node is being inserted */ *current = new_node;
Time Complexity: O(n)
Auxiliary Space: O(1) because it is using constant space
Source: https://www.geeksforgeeks.org/given-a-linked-list-which-is-sorted-how-will-you-insert-in-sorted-way/
0 Response to "Continue Traversing Linked List After Finding Match C"
Post a Comment