REORDER LIST

Concepts Used

Linked List.

Difficulty Level

Hard.

Problem Statement :

Given a singly linked list L:L0→L1→…→Ln−1→Ln,
reorder it to :L0→Ln→L1→Ln−1→L2→Ln−2→…
You must do this in-place without altering the nodes’ values.
Expected Time Complexity O(n).

See original problem statement here

Example:

 Given 1->2->3->4,
  reorder it to 1->4->2->3.

EXPLANATION:

Approach 1(Brute force):

Initialize the current node as head.

While next of current node is not null,find the last node, remove it from the end and insert it as next of the current node.

Move current to next of current.

TIME COMPLEXITY: O(n*n)

Approach 2(Efficient solution):

This approach uses two pointers(tortoise and hare method) to find the middle of linked list.Reverse the second half and alternately merge the first and second halves.

Approach 3(Deque):

1) Create an empty deque.

2) Insert all element from the linked list to the deque.

3) Insert the element back to the linked list from deque in alternate fashion i.e first then last and so on.

SOLUTIONS:

#include 
#include
struct Node { 
    int data; 
    struct Node* next; 
}; 

// Function to create newNode in a linkedlist 
struct Node* newNode(int key) 
{ 
    struct Node* temp;
    temp=(struct Node *)malloc(sizeof(struct Node));
    temp->data = key; 
    temp->next = NULL; 
    return temp; 
} 

// Function to reverse the linked list 
void reverselist(struct Node** head) 
{ 
    // Initialize prev and current pointers 
    struct Node *prev = NULL, *curr = *head, *next; 

    while (curr) { 
        next = curr->next; 
        curr->next = prev; 
        prev = curr; 
        curr = next; 
    } 

    *head = prev; 
} 

// Function to print the linked list 
void printlist(struct Node* head) 
{ 
    while (head != NULL) { 
        printf("%d ",head->data); 
        if (head->next) 
            printf(" "); 
        head = head->next; 
    } 
    printf("\n"); 
} 

    void rearrange(struct Node** head) 
    { 
    // 1) Find the middle point using tortoise and hare method 
    struct Node *slow = *head, *fast = slow->next; 
    while (fast && fast->next) { 
        slow = slow->next; 
        fast = fast->next->next; 
    } 
    struct Node* head1 = *head; 
    struct Node* head2 = slow->next; 
    slow->next = NULL; 

    reverselist(&head2); 

    *head = newNode(0); 
    struct Node* curr = *head; 
    while (head1 || head2) { 
        if (head1) { 
            curr->next = head1; 
            curr = curr->next; 
            head1 = head1->next; 
        } 
        if (head2) { 
            curr->next = head2; 
            curr = curr->next; 
            head2 = head2->next; 
        } 
    } 

    // Assign the head of the new list to head pointer 
    *head = (*head)->next; 
    } 
     int main() 
    {   int n;scanf("%d",&n);
   int x;scanf("%d",&x);

    struct Node* head = newNode(x); 
    struct Node* headlist=head;
    for(int i=1;inext=newNode(x);
      head=head->next;
    }
    //head->next=NULL;
    printf("%d ",headlist->data);
    rearrange(&headlist); // Modify the list 
    printlist(head); // Print modified list 
    return 0; 
    } 
#include  
using namespace std; 
struct Node { 
    int data; 
    struct Node* next; 
}; 

// Function to create newNode in a linkedlist 
Node* newNode(int key) 
{ 
    Node* temp = new Node; 
    temp->data = key; 
    temp->next = NULL; 
    return temp; 
} 

// Function to reverse the linked list 
void reverselist(Node** head) 
{ 
    // Initialize prev and current pointers 
    Node *prev = NULL, *curr = *head, *next; 

    while (curr) { 
        next = curr->next; 
        curr->next = prev; 
        prev = curr; 
        curr = next; 
    } 

    *head = prev; 
} 

// Function to print the linked list 
void printlist(Node* head) 
{ 
    while (head != NULL) { 
        cout << head->data << " "; 
        if (head->next) 
            cout << " "; 
        head = head->next; 
    } 
    cout << endl; 
} 

    void rearrange(Node** head) 
    { 
    // 1) Find the middle point using tortoise and hare method 
    Node *slow = *head, *fast = slow->next; 
    while (fast && fast->next) { 
        slow = slow->next; 
        fast = fast->next->next; 
    } 
    Node* head1 = *head; 
    Node* head2 = slow->next; 
    slow->next = NULL; 

    reverselist(&head2); 

    *head = newNode(0); 
    Node* curr = *head; 
    while (head1 || head2) { 
        if (head1) { 
            curr->next = head1; 
            curr = curr->next; 
            head1 = head1->next; 
        } 
        if (head2) { 
            curr->next = head2; 
            curr = curr->next; 
            head2 = head2->next; 
        } 
    } 

    // Assign the head of the new list to head pointer 
    *head = (*head)->next; 
    } 
     int main() 
    {   int n;cin>>n;
   int x;cin>>x;

    Node* head = newNode(x); 
    Node* headlist=head;
    for(int i=1;i>x;
      head->next=newNode(x);
      head=head->next;
    }
    //head->next=NULL;
    cout<data<<" ";
    rearrange(&headlist); // Modify the list 
    printlist(head); // Print modified list 
    return 0; 
    } 
import java.util.*; 
    import java.lang.*; 
    import java.io.*; 

    class prepbytes
    { 
    static class Node  
    {  
        int data;  
        Node next; 
        Node(int data) 
        { 
            this.data = data; 
            next = null; 
        } 
    } 
    static void printList(Node head)  
    {  
        Node temp = head;  
        while (temp != null)  
        {  
            System.out.print(temp.data + " ");  
            temp = temp.next;  
        }  
    } 
    static void arrange(Node head) 
    { 
        Deque deque = new ArrayDeque<>(); 
        Node temp = head; 
        while(temp != null) 
        { 
            deque.addLast(temp.data); 
            temp = temp.next; 
        } 
        temp = head; 
        int i = 0; 
        while(!deque.isEmpty()) 
        { 
            if(i % 2 == 0) 
            { 
                temp.data = deque.removeFirst(); 
            } 
            else
            { 
                temp.data = deque.removeLast(); 
            } 
            i++; 
            temp = temp.next; 
        } 
    } 
    public static void main (String[] args) 
    { Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
         int x = sc.nextInt();
        Node head = new Node(x);
        Node headlist=head;
            for(int i=1;i
						 

class Node:

	def __init__(self, d):
		self.data = d
		self.next = None
		
def printlist(node):
	if(node == None):
		return
	while(node != None):
		print(node.data," -> ", end = "")
		node = node.next

def reverselist(node):
	prev = None
	curr = node
	next=None
	while (curr != None):
		next = curr.next
		curr.next = prev
		prev = curr
		curr = next
	node = prev
	return node

def rearrange(node):

	slow = node
	fast = slow.next
	while (fast != None and fast.next != None):
		slow = slow.next
		fast = fast.next.next
	
	node1 = node
	node2 = slow.next
	slow.next = None
	
	node2 = reverselist(node2)
	
	node = Node(0) 
	
	curr = node
	
	while (node1 != None or node2 != None):
		
		if (node1 != None):
			curr.next = node1
			curr = curr.next
			node1 = node1.next
		
		if(node2 != None):
			curr.next = node2
			curr = curr.next
			node2 = node2.next
	
	node = node.next

head = None
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

printlist(head) 
rearrange(head) 
print()
printlist(head) 

[forminator_quiz id="1827"]

This article tried to discuss reordering the given Linked List. Hope this blog helps you understand and solve the problem. To practice more problems on Linked List you can check out MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *