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

Thursday 2 May 2019

Move last element to the 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 Linked List is 1->2->3->4->5, 
 Output Linked List is 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 second last node.

 After the end of loop do 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 (*head_ref == NULL || (*head_ref)->next == NULL)
        return;

    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;
    }

    secLast->next = NULL;

    last->next = *head_ref;

    *head_ref = last;
}


void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node =
        (struct Node*) malloc(sizeof(struct Node));

    new_node->data  = new_data;

    new_node->next = (*head_ref);

    (*head_ref) = new_node;
}

void printList(struct Node *node)
{
    while(node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}

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

    /* The constructed linked list is:
     1->2->3->4->5 */
    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