Linked List

 avatar
tuhuuduc
c_cpp
24 days ago
3.1 kB
2
Indexable
Never
#include <iostream>
using namespace std;
class Node
{
public:
   int data;
   Node *next;
};
//insert a new node in front of the list
void push(Node** head, int node_data)
{
    Node* newNode = new Node;
    newNode->data = node_data;
    newNode->next = (*head);
    (*head) = newNode;
}
void insertAfter(Node* prev_node, int node_data)
{
    if (prev_node == NULL)
    {
       cout<<"the given previous node is required,cannot be NULL";
       return;
    } 
    struct Node* newNode =new Node; 
    newNode->data = node_data;
    newNode->next = prev_node->next;
    prev_node->next = newNode;
}
void append(Node** head, int node_data)
{
    Node* newNode = new Node;
    Node *last = *head; 
    newNode->data = node_data;
    newNode->next = NULL;
    if (*head == NULL)
    {
        *head = newNode;
        return;
    }

    while (last->next != NULL)
        last = last->next;

    last->next = newNode;
    return;
}

Node* deleteFirstNode(Node* head)
{
   if (head == NULL)
   return NULL;

   Node* tempNode = head;
   head = head->next;
   delete tempNode;
 
   return head;
}

Node* removeLastNode(Node* head)
{
   if (head == NULL)
   return NULL;
 
   if (head->next == NULL) {
      delete head;
      return NULL;
   }
 
    Node* second_last = head;
    while (second_last->next->next != NULL)
        second_last = second_last->next;

    delete (second_last->next);
    second_last->next = NULL;
    return head;
}

Node* findNode(Node *node, int val){
    while(node != NULL && node->data!=val){
        node = node->next;
    }
    return node;
}

Node* removeDuplicate(Node* head){
    Node* current = head;
    Node* nextNode;

    while(current != nullptr && current->next != nullptr){
        nextNode = current;
        while(nextNode->next != nullptr){
            if(current->data == nextNode->next->data){
                Node* duplicate = nextNode->next;
                nextNode->next = nextNode->next->next;
                delete duplicate;
            } else {
                nextNode = nextNode->next;
            }
        }
        current = current->next;
    }
    return head;
}

 

void displayList(Node *node)
{
    while (node != NULL)
    {
      cout<<node->data<<"-->";
      node = node->next;
    }
 
    if(node== NULL)
    cout<<"null\n"; 
}

int main() 
{ 
    Node* head = NULL; 
    append(&head, 10); 
    push(&head, 20);
    push(&head, 10);
    push(&head, 30); 
    push(&head, 20);
    push(&head, 30); 
    append(&head, 40); 
    append(&head, 40); 
    insertAfter(head->next, 50);

    cout<<"Final linked list: "<<endl;
    displayList(head);
    removeDuplicate(head);
    cout<<"Linked list after remove duplicate"<<endl; 
    displayList(head);
    head = deleteFirstNode(head);
    cout<<"Linked list after deleting head node"<<endl;
    displayList(head);
    head = removeLastNode(head);
    cout<<"Linked list after deleting last node"<<endl; 
    displayList(head);
    
    return 0;
}
Leave a Comment