INPUT : Show OUTPUT : Time Complexity : O(n) Algorithm1. Find the middle point using tortoise and hare method b. By the end of the list, slow will point to the middle point of the linkedlist 2. Split the linked list into two halves using the middle point 3. Reverse the second half 4. Do alternate merge of first and second halves Implementation of Algorithm for above example 1. Middle point is the node 3 2. list1 = 1->2->3, list2 = 4->5 3. Reverse the second list. 4. Alternate Merge C++ Program#include <bits/stdc++.h>
using namespace std;
struct LLNode{
int data;
LLNode *next;
};
// Function to create newNode in a linkedlist
LLNode* newNode(int data)
{
LLNode *temp = new LLNode;
temp->data = data;
temp->next = NULL;
return temp;
}
// Function to reverse the linked list
void reverselist(LLNode **head)
{
// Initialize prev and current pointers
LLNode *prev = NULL, *curr = *head, *next;
while (curr)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
// Function to rearrange a linked list
void rearrange(LLNode **head)
{
// 1) Find the middle point using tortoise and hare method
LLNode *slow = *head, *fast = slow->next;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
// 2) Split the linked list in two halves
LLNode *list1 = *head;
LLNode *list2 = slow->next;
slow->next = NULL;
// 3) Reverse the second half
reverselist(&list2);
// 4) Merge alternate nodes
*head = newNode(0); // Assign dummy Node
// curr is the pointer to this dummy Node, which will
// be used to form the new list
LLNode *result = *head;
while (list1 || list2)
{
// First add the element from first list
if (list1)
{
result->next = list1;
result = result->next;
list1 = list1->next;
}
// Then add the element from second list
if (list2)
{
result->next = list2;
result = result->next;
list2 = list2->next;
}
}
// Assign the head of the new list to head pointer
*head = (*head)->next;
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;
if(*head==NULL) //if list is empty then set the current formed node as head of list
*head=curr;
else //make the next of the current node point to the present head and make the current node as the new head
{
curr->next=*head;
*head=curr;
}
//O(1) constant time
}
void display(LLNode**head)
{
LLNode*temp=*head;
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;
temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
int main()
{
LLNode *head = NULL; //initial list has no elements
insertAtBeginning(&head,5);
insertAtBeginning(&head,4);
insertAtBeginning(&head,3);
insertAtBeginning(&head,2);
insertAtBeginning(&head,1);
cout<<"\nCurrent List is :-\n";
display(&head);
rearrange(&head);
cout<<"After rearranging the elements"<<endl;
display(&head);
return 0;
} 
Rearrange a linked list into alternate fashion first and the last element This article will explain how to rearrange the linked list into alternate fashion first and the last element. Here, we have given a singly linked list, and we need to arrange the given linked list alternately, like the first element, then the last element, and so on. Example: - Input: 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 Output: 2 -> 16 -> 4 -> 14 -> 6 -> 12 -> 8 -> 10 Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 1 -> 5 -> 2 -> 4 -> 3 Method: We can do this by using the following steps:
Java program to rearrange a linked list into alternate fashion first and last element import java.util.*; class Node { int data; Node next; Node(int d) { data = d; next = null; } } public class RearrangeLinkedList { Node head, second; /* Function to print linked list */ void traverse(Node head) { Node temp = head; while (temp != null) { System.out.print(temp.data+" "); temp = temp.next; } System.out.println(); } /* Function for reverse the linked list */ Node reverse(Node temp) { Node prev = null; Node current = temp; Node next; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } return prev; } // Function for find the middle node of the linked list public static Node findMiddle(Node head) { Node prev = null; Node slow = head, fast = head; // find the middle pointer while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } // for odd nodes, fix middle if (fast != null && fast.next == null) { prev = slow; slow = slow.next; } // make next of previous node null prev.next = null; // return middle node return slow; } // Function for rearranging the linked list in an alternate fashion public void rearrange(Node head) { if (head == null) return; Node middle = findMiddle(head); second = reverse(middle); head=merge(head, second); } // Function for merge the first and second halves of the linked list public Node merge(Node first, Node second) { if (first == null) { return second; } if (second == null) { return first; } Node recursion = merge(first.next, second.next); Node res = first; first.next = second; second.next = recursion; return res; } // Driver Function public static void main(String args[]) { Scanner sc = new Scanner(System.in); System.out.println("Enter the total no of elements in linked list: "); int n = sc.nextInt(); System.out.println("Enter the elements of linked list: "); int a1 = sc.nextInt(); RearrangeLinkedList ob = new RearrangeLinkedList(); Node head = new Node(a1); Node tail = head; for (int i = 1; i < n; i++) { int a = sc.nextInt(); tail.next = new Node(a); tail = tail.next; } ob.rearrange(head); System.out.print("Rearranged List:-"); ob.traverse(head); } }Output: Time Complexity: The time complexity of this method is O(n). |
Rearrange linked list in alternate last and first
Pos Terkait
Copyright © 2024 toptenid.com Inc.
