Last Updated: 13 Feb, 2021
Deleting and Adding the last node
Easy
Asked in companies
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:
Please note that the linked list will only contain numeric values.
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
Approaches
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:
- If the given linked list is empty or has only one element, then return head.
- Declare two-node type variables (assume ‘P’ and ‘Q’), first to hold the second last node and other to the last node.
- Initially, set both the variables to the head.
- 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 - Now, assign ‘P’ ->next = NULL because after deleting the last node, this node becomes the last.
- Make sure that now, ‘Q’ will point to the head.
- Return ‘Q’.