Append the last n nodes of a linked list to the beginning of the list
Java program to append last n nodes to the beginning
Java program to append last n nodes to the beginning of the Linked List. Last n nodes of the linked list will be placed in the beginning of the list.
Example:
Input : 10–>20–>30–>40–>50–>60
n=3
Output: 40–>50–>60–>10–>20–>30
Algorithm to append last n nodes to the beginning
- Find (n+1)th node from the end of linked list. It will be the tail of modified linked list.
- Find nth node from the beginning of linked list. It will be the head of modified linked list.
- Set the next of (n+1)th node as null.
- Point the next of the tail of original linked list to head of original linked list.
- Change head and tail of the original linked list accordingly.
Example
Input : 10-->20-->30-->40-->50-->60
n=3
Output: 40-->50-->60-->10-->20-->30
Code in JAVA Programming Language
Run
import java.util.*;
public class Main
{
public static void main (String[]args) throws Exception
{
LinkedList ll = new LinkedList ();
ll.addFirst (60);
ll.addFirst (50);
ll.addFirst (40);
ll.addFirst (30);
ll.addFirst (20);
ll.addFirst (10);
ll.display ();
ll.appendToFront (3);
ll.display ();
}
}
class LinkedList
{
private class Node
{
int data;
Node next;
// Node constructor
// There are two fields in the node- data and address of next node
public Node (int data, Node next)
{
this.data = data;
this.next = next;
}
}
private Node head;
private Node tail;
private int size;
// Linked list constructor
public LinkedList ()
{
this.head = null;
this.tail = null;
this.size = 0;
}
// Function to find the size of linked list
public int size ()
{
return this.size;
}
// Function to check whether linked list is empty or not
public boolean isEmpty ()
{
return this.size () == 0;
}
// Function to traverse and print the linked list
public void display ()
{
Node temp = head;
while (temp != null)
{
System.out.print (temp.data + ">");
// Set temp to point to the next node
temp = temp.next;
}
System.out.println ("END");
}
// Function to add a node in beginning of linked list
public void addFirst (int item)
{
// Create a temp node which points to head
Node temp = new Node (item, head);
// If linked list is empty, temp is the head and tail node both
if (this.size == 0)
{
this.head = this.tail = temp;
}
// else set the head such that it now points to temp node
else
{
this.head = temp;
}
this.size++;
}
public int kthFromLast (int k)
{
return this.kthNodeFromLast (k).data;
}
// Function to find kth node from last
private Node kthNodeFromLast (int k)
{
// Take slow and fast pointers
Node slow = this.head;
Node fast = this.head;
// First move fast pointer k nodes from the head
for (int i = 0; i < k; i++)
{
fast = fast.next;
}
// Move both slow and fast by one till fast becomes null
while (fast != null)
{
fast = fast.next;
slow = slow.next;
}
// Slow pointer points to the nth node from last
return slow;
}
public void appendToFront (int n)
{
// Find (n+1)th node from last
Node np1 = this.kthNodeFromLast (n + 1);
// Find the nth node from beginning
Node nth = np1.next;
// Set the pointers of node
np1.next = null;
this.tail.next = this.head;
this.head = nth;
this.tail = np1;
}
}
Output: 10–>20–>30–>40–>50–>60–>END 40–>50–>60–>10–>20–>30–>END
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Singly Linked List
- Introduction to Linked List in Data Structure
Click Here - Linked List in –
- Singly Linked List in –
- Insertion in singly Linked List –
- Insertion at beginning in singly Linked List –
- Insertion at nth position in singly Linked List –
- Insertion at end in singly Linked List –
- Deletion in singly Linked List –
- Deletion from beginning in singly linked list :
- Deletion from nth position in singly linked list :
- Deletion from end in singly linked list :
- Linked List Insertion and Deletion –
C | C++ | Java - Reverse a linked list without changing links between nodes (Data reverse only) –
C | C++ | Java - Reverse a linked list by changing links between nodes –
- Print reverse of a linked list without actually reversing –
- Print reverse of a linked list without actually reversing –
- Insertion in the middle Singly Linked List –
- Insertion in a Sorted Linked List –
- Delete alternate nodes of a Linked List –
- Find middle of the linked list –
- Reverse a linked list in groups of given size –
- Find kth node from end of the linked list –
- Append the last n nodes of a linked list to the beginning of the list –
- Check whether linked list is palindrome or not –
- Fold a Linked List –
- Insert at given Position –
- Deletion at given Position –
Singly Linked List
- Introduction to Linked List in Data Structure
- Linked List in – C | C++ | Java
- Singly Linked List in – C | C++ | Java
- Insertion in singly Linked List – C | C++ | Java
- Deletion in singly Linked List – C | C++ | Java
- Reverse a linked list without changing links between nodes (Data reverse only) – C | C++ | Java
- Linked List Insertion and Deletion – C | C++ | Java
- Reverse a linked list by changing links between nodes – C | C++ | Java
- Linked List insertion in the middle – C | C++ | Java
- Print reverse of a linked list without actually reversing – C |C++ | Java
- Search an element in a linked list – C | C++ | Java
- Insertion in a Sorted Linked List – C | C++ | Java
- Delete alternate nodes of a Linked List – C | C++ | Java
- Find middle of the linked list – C | C++ | Java
- Reverse a linked list in groups of given size – C | C++ | Java
- Find kth node from end of the linked list – C | C++ | Java
- Append the last n nodes of a linked list to the beginning of the list – C | C++ | Java
- Check whether linked list is palindrome or not – C | C++ | Java
- Fold a Linked List – C | C++ | Java
- Insert at a given position – C | C++ | Java
- Delete at a given position – C | C++ | Java
