Deleting and Adding the last node

Easy
0/40
Average time to solve is 10m
profile
Contributed by
13 upvotes
Asked in companies
Dream11GeekyAnts Software Pvt LtdAmdocs

Problem statement

You are provided with a singly linked list, all you have to do is to delete the last node of the linked list and add it to the front of the linked list.

Example:

Example

Please note that the linked list will only contain numeric values.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain the elements of the linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
Output Format: 
For each test case, return the new head node of the linked list after adding the last node to its front.

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything, It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
0 <= N <= 10000
-10^4 <= LIST[i] <= 10^4

Where 'N' is the total number of nodes in the given linked list. ‘LIST[i]’ represents the node value of the node ‘i’.

Time limit: 1 sec
Sample Input 1:
2
2 5 3 11 1 -1
2 -1
Sample Output 1:
1 2 5 3 11 -1
2 -1
Explanation of Sample Output 1:
In test case 1, the new linked list after doing delete and add operations to the last node: 1 2 5 3 11 -1.

In test case 2, the linked list has only one node and so, the last node is itself at the front.
Sample Input 2:
2
4 3 -1
1 1 1 1 -1
Sample Output 2:
3 4 -1
1 1 1 1 -1
Explanation for Sample Output 2:
In test case 1, the new linked list after doing delete and add operations to the last node: 3 4 -1.

In test case 2, the new linked list after swapping first and last nodes: 1 1 1 1 -1.
Hint

Can you break the linked list into two parts?

Approaches (1)
Brute Force

The basic idea is to break the linked list into two parts at the second last node position and then swap both halves. 

 

The Steps are as follows:

 

  1. If the given linked list is empty or has only one element, then return head.
  2. Declare two-node type variables (assume ‘P’ and ‘Q’), first to hold the second last node and other to the last node.
  3. Initially, set both the variables to the head.
  4. Now, Keep changing the ‘Q’ variable to the next and ‘P’ to the second until the second reaches the NULL value.
    while('Q'->next != NULL) => ‘P’ = ‘Q’, ‘Q’ = ‘Q’ -> next
  5. Now, assign ‘P’ ->next = NULL because after deleting the last node, this node becomes the last.
  6. Make sure that now, ‘Q’ will point to the head.
  7. Return ‘Q’.
Time Complexity

O(N), Where ‘N’ is the length of the given linked list.

 

Since we are iterating through the list once, so the overall time complexity will be O(N).

Space Complexity

O(1)

 

Since we are not using any extra space, so the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Deleting and Adding the last node
Full screen
Console