Posted on by Kalkicode

# Move last node to front in linked list

The problem revolves around manipulating a singly linked list. In particular, the task is to move the last node of the linked list to the front. A singly linked list is a linear data structure where each element (node) holds a value and a reference to the next element. The last node is the one whose "next" pointer points to NULL.

## Problem Statement and Description

Given a singly linked list, we want to reorganize it such that the last node becomes the new head while maintaining the order of other nodes. For instance, if we have the linked list 1 → 2 → 3 → 4 → 5, the result should be 5 → 1 → 2 → 3 → 4.

## Example

Let's take the example of the linked list: 1 → 2 → 3 → 4 → 5 → 6 → 7.

• Before Moving Last Node
• Linked List: 1 → 2 → 3 → 4 → 5 → 6 → 7
• Explanation: This is how the linked list looks before moving the last node to the front.
• After Moving Last Node
• Linked List: 7 → 1 → 2 → 3 → 4 → 5 → 6
• Explanation: The last node, which was 7, is now moved to the front while maintaining the order of other nodes.

## Idea to Solve

1. Traverse the linked list to find the second-to-last node. This can be achieved by iterating until the next node's next pointer is not NULL.
2. Once the second-to-last node is found, adjust the pointers to move the last node to the front.
3. Update the new head and set the last node's next pointer to NULL to break the linked list.

## Pseudocode

``````moveLastNode(ref):
return

while temp is not NULL and temp.next is not NULL and temp.next.next is not NULL:
temp = temp.next

temp.next = NULL``````

## Algorithm Explanation

1. Check if the linked list is empty or contains only one node. In such cases, there's no need to move the last node to the front, so just return.
2. Initialize a temporary pointer `temp` to point to the head of the linked list.
3. Traverse the linked list using the `temp` pointer to find the second-to-last node. The loop condition checks for `temp` being not NULL and having at least two more nodes ahead.
4. After exiting the loop, the `temp` pointer will be pointing to the second-to-last node.
5. Adjust the pointers to move the last node to the front: Set the `next` pointer of the last node (previously the second-to-last node) to point to the head node.
6. Update the head of the linked list to the last node, making it the new head.
7. Set the `next` pointer of the second-to-last node (now the new last node) to NULL, effectively breaking the linked list.

## Time Complexity

• The algorithm involves traversing the linked list to find the second-to-last node. This takes O(n) time, where n is the number of nodes in the linked list.
• The rest of the operations involve adjusting pointers, which are constant-time operations.
• Hence, the overall time complexity of the algorithm is O(n).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post