Interviews Questions, Algorithms, Aptitude, C Interview Program, C Theory Question, Aptitude Tricks, Test Series,

Saturday, 27 April 2019

Move last element to front of a given Linked List

Question:
Write a function that moves the last element to the front in a given Singly Linked List.

 For example:

Input: 1->2->3->4->5

Output: 5->1->2->3->4.



Algorithm:

Traverse the list till the last node. Use two pointers: one to store the address of the last node and other for the address of the second last node. After the end of the loop do the following operations.
i) Make second last as last (secLast->next = NULL).
ii) Set next of last as head (last->next = *head_ref).
iii) Make last as head ( *head_ref = last)



 C Program :

#include<stdio.h>
#include<stdlib.h>
struct Node
{
    int data;
    struct Node *next;
};

void moveToFront(struct Node **head_ref)
{
    /* If linked list is empty, or it contains only one node,
      then nothing needs to be done, simply return */
    if (*head_ref == NULL || (*head_ref)->next == NULL)
        return;

    /* Initialize second last and last pointers */
    struct Node *secLast = NULL;
    struct Node *last = *head_ref;

    /*After this loop secLast contains address of second last
    node and last contains address of last node in Linked List */
    while (last->next != NULL)
    {
        secLast = last;
        last = last->next;
    }

    /* Set the next of second last as NULL */
    secLast->next = NULL;

    /* Set next of last as head node */
    last->next = *head_ref;

    /* Change the head pointer to point to last node now */
    *head_ref = last;
}

/* UTILITY FUNCTIONS */
/* Function to add a node at the begining of Linked List */
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node =
        (struct Node*) malloc(sizeof(struct Node));

    /* put in the data  */
    new_node->data  = new_data;

    /* link the old list off the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}


/* Function to print nodes in a given linked list */
void printList(struct Node *node)
{
    while(node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}

int main()
{
    struct Node *start = NULL;

    push(&start, 5);
    push(&start, 4);
    push(&start, 3);
    push(&start, 2);
    push(&start, 1);

    printf("\n Linked list before moving last to the front\n");
    printList(start);

    moveToFront(&start);

    printf("\n Linked list after removing last to the  front\n");
    printList(start);

    return 0;
}


Output:
 Linked list before moving last to the front
1 2 3 4 5
 Linked list after removing last to the front
5 1 2 3 4



0 comments:

Post a Comment