Reverse alternate K nodes in a Linked List

Reverse alternate K nodes in a Linked List

Here given code implementation process.

//C Program
//Reverse alternate K nodes in a Linked List
#include <stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node
{
  int data;
  struct Node*next;
};

//insert Node element
void insert(struct Node**head,int value)
{
  //Create dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));

  if(node==NULL)
  {
    printf("Memory overflow\n");
  }else
  {
    node->data=value;
    node->next=NULL;
    if(*head==NULL)
    {
      *head=node;
    }
    else
    {
      struct Node*temp=*head;
      //find last node
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add node at last possition
      temp->next=node;
    }
  }
}
//Display element of Node
void display(struct Node*temp)
{

  if(temp==NULL)
  {
    printf("Empty linked list");
  }
  while(temp!=NULL)
  {
    printf("%d  ",temp->data);
    temp=temp->next;
  }
}



struct Node* reverse_k(struct Node*head,int k)
{
  if(head==NULL || k<=1)
  {
    return head;
  }
  printf("\nReverse alternate %d nodes",k);

  struct Node*auxiliary=NULL,
  *temp=head,
  *back=NULL,
  *current=head,
  *root=head,
  *first=NULL;
  int move=1, size=0;
  while(temp!=NULL)
  {
    size++;

    if(size==k)
    {
      
     if(move==1)
     {

      temp=temp->next;
      back=temp;
      root=current;

      if(current!=head)
      {
        current=current->next;
      }
      while(current != NULL && size > 0)
      {

        auxiliary = current->next;
        current->next = back;
        back = current;
        current = auxiliary;
        size--;
      }
      if(root==head)
      {
        head=back;
      }
      else
      {
        root->next=back;
      }
        move=0;
     }
     else
     {
       current=temp;
       temp=temp->next;
       move=1;
       size=0;
     } 
    }
    else
    {
      temp=temp->next;
    }
  }

  return head;
}

int main()
{
  //Create node pointer
  struct Node*head=NULL;

  //Insert element of linked list
  insert(&head,1);
  insert(&head,2);
  insert(&head,3);
  insert(&head,4);
  insert(&head,5);
  insert(&head,6);
  insert(&head,7);
  insert(&head,8);
  insert(&head,9);
  insert(&head,10);
  //display all node
  display(head);

  int k=3;

  head=reverse_k(head,k);

  printf("\n");

  display(head);
  return 0;
}

Output

1  2  3  4  5  6  7  8  9  10  
Reverse alternate 3 nodes
3  2  1  4  5  6  9  8  7  10
//C++ Program 
//Reverse alternate K nodes in a Linked List
#include <iostream>
using namespace std;

//Create structure
struct Node
{
  int data;
  struct Node*next;
};
class LinkedList
{

public:
  Node*head;//head node
  LinkedList();
  void insert(int);
  void display();
  void reverse_k(int);
};
LinkedList::LinkedList()
{
  head=NULL;
}
//insert node at end of linked list
void LinkedList::insert(int value)
{
  //Create dynamic node
  Node*node=new Node;
  if(node==NULL)
  {
    cout<<"Memory overflow\n";
  }else
  {
    node->data=value;
    node->next=NULL;
    if(head==NULL)
    {
      //base condition
      head=node;
    }else
    {
      Node*temp=head;
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add newly node at last
      temp->next=node;
    }
  }
}
//display all node value in linked list
void LinkedList:: display()
{
  if(head==NULL)
  {
    cout<<"Empty linked list";
  }
  else
  {
    Node*temp=head;
    cout<<"Linked List : ";
    while(temp!=NULL)
    {
      //print node value
      cout<<temp->data<<" ";
      temp=temp->next;
    }
  }
}
void LinkedList :: reverse_k(int k)
{
  if(head==NULL || k<=1)
  {
    return;
  }
  cout<<"\nReverse alternate "<<k <<" nodes"<<endl;

  Node*auxiliary=NULL,
  *temp=head,
  *back=NULL,
  *current=head,
  *root=head,
  *first=NULL;
  int move=1, size=0;
  while(temp!=NULL)
  {
    size++;

    if(size==k)
    {
      
     if(move==1)
     {

      temp=temp->next;
      back=temp;
      root=current;

      if(current!=head)
      {
        current=current->next;
      }
      while(current != NULL && size > 0)
      {

        auxiliary = current->next;
        current->next = back;
        back = current;
        current = auxiliary;
        size--;
      }
      if(root==head)
      {
        head=back;
      }
      else
      {
        root->next=back;
      }
        move=0;
     }
     else
     {
       current=temp;
       temp=temp->next;
       move=1;
       size=0;
     } 
    }
    else
    {
      temp=temp->next;
    }
  }
}
int main()
{
  //create object
  LinkedList obj;

  //Insert element of linked list
  obj.insert(1);
  obj.insert(2);
  obj.insert(3);
  obj.insert(4);
  obj.insert(5);
  obj.insert(6);
  obj.insert(7);
  obj.insert(8);
  obj.insert(9);
  obj.insert(10);
  //display all node
  obj.display();

  int k=3;

  obj.reverse_k(k);

  //display all node
  obj.display();
  return 0;
}

Output

Linked List : 1 2 3 4 5 6 7 8 9 10 
Reverse alternate 3 nodes
Linked List : 3 2 1 4 5 6 9 8 7 10
//Java program
//Reverse alternate K nodes in a Linked List
public class LinkedList
{

  static class Node
  {
    int data;
    Node next;
  }
  public Node head;
  //Class constructors
  LinkedList()
  {
    head=null;
  } 
  //insert  element
  public void insert(int value)
  {
    //Create  node
    Node node=new Node();
    node.data=value;
    node.next=null;
    if(head==null) head=node;
    else
    {
      Node temp=head;
      //find last node
      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=node;
    }
    
  }
  //Display all Linked List elements
  public void display()
  {
    if(head!=null)
    {
      System.out.print("Linked List Element :");
      Node temp=head;
      while(temp!=null)
      {
        System.out.print("  "+temp.data);
        temp=temp.next;
      }
      System.out.println();
    }
    else
    {
      System.out.println("Empty Linked list"); 
    }
  }
  public void reverse_k(int k)
  {
    if(head==null || k<=1)
    {
      return;
    }
    System.out.println("Reverse alternate "+k+" nodes");

    Node auxiliary=null,
    temp=head,
    back=null,
    current=head,
    root=head,
    first=null;
    int move=1, size=0;
    while(temp!=null)
    {
      size++;

      if(size==k)
      {

        if(move==1)
        {

          temp=temp.next;
          back=temp;
          root=current;

          if(current!=head)
          {
            current=current.next;
          }
          while(current != null && size > 0)
          {

            auxiliary = current.next;
            current.next = back;
            back = current;
            current = auxiliary;
            size--;
          }
          if(root==head)
          {
            head=back;
          }
          else
          {
            root.next=back;
          }
          move=0;
        }
        else
        {
          current=temp;
          temp=temp.next;
          move=1;
          size=0;
        } 
      }
      else
      {
        temp=temp.next;
      }
    }
  }

  public static void main(String[] args) 
  {

    LinkedList obj = new LinkedList();
    //Insert element of linked list
    obj.insert(1);
    obj.insert(2);
    obj.insert(3);
    obj.insert(4);
    obj.insert(5);
    obj.insert(6);
    obj.insert(7);
    obj.insert(8);
    obj.insert(9);
    obj.insert(10);
    //display all node
    obj.display();

    int k=3;

    obj.reverse_k(k);
    //display all node
    obj.display();
  }
}

Output

Linked List Element :  1  2  3  4  5  6  7  8  9  10
Reverse alternate 3 nodes
Linked List Element :  3  2  1  4  5  6  9  8  7  10
Reverse alternate K nodes
#Python Program 
#Reverse alternate K nodes in a Linked List
class Node:
  def __init__(self,data):
    self.data=data
    self.next=None

#create class Linked    
class LinkedList:

  def __init__(self):

    #Assign default value
    self.head=None

  #insert new node to Linked  
  def insert(self,data):

    node=Node(data)

    if(self.head==None):
      #first element of linked list
      self.head=node
    else:
    
      temp=self.head
      #find middle node of linked list
      while(temp!=None and temp.next!=None ):
        temp=temp.next
      
      #add at last of linked list  
      temp.next=node 
   

  #display all linked list node 
  def display(self):
    temp=self.head
    while(temp!=None):
      print(temp.data,end=" ")
      temp=temp.next
    print()

  def reverse_k(self,k):
    if(self.head==None  or  k<=1):
      return
    
    print("Reverse alternate",k,"nodes")

    auxiliary=None
    temp=self.head
    back=None
    current=self.head
    root=self.head
    first=None
    move=1 
    size=0
    while(temp!=None):
      size+=1

      if(size==k):

        if(move==1):

          temp=temp.next
          back=temp
          root=current

          if(current!=self.head):
            current=current.next
          
          while(current != None  and  size > 0):

            auxiliary = current.next
            current.next = back
            back = current
            current = auxiliary
            size-=1
          
          if(root==self.head):
            self.head=back
          
          else:
            root.next=back
          
          move=0
        
        else:
          current=temp
          temp=temp.next
          move=1
          size=0
         
      
      else :
        temp=temp.next
      

def main():
  obj = LinkedList()
  #Insert element of linked list
  obj.insert(1)
  obj.insert(2)
  obj.insert(3)
  obj.insert(4)
  obj.insert(5)
  obj.insert(6)
  obj.insert(7)
  obj.insert(8)
  obj.insert(9)
  obj.insert(10)
  #display all node
  obj.display()

  k=3

  obj.reverse_k(k)
  #display all node
  obj.display()

if __name__ =="__main__":
  main()

Output

1 2 3 4 5 6 7 8 9 10 
Reverse alternate 3 nodes
3 2 1 4 5 6 9 8 7 10 
//C# program
//Reverse alternate K nodes in a Linked List

using System;
public class Node
{
  public int data;
  public Node next;
}
public class LinkedList
{


  public Node head;
  //Class constructors
  LinkedList()
  {
    head=null;
  } 
  //insert  element
  public void insert(int value)
  {
    //Create  node
    Node node=new Node();
    node.data=value;
    node.next=null;
    if(head==null) head=node;
    else
    {
      Node temp=head;
      //find last node
      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=node;
    }

  }
  //Display all Linked List elements
  public void display()
  {
    if(head!=null)
    {
      Console.Write("Linked List Element :");
      Node temp=head;
      while(temp!=null)
      {
        Console.Write("  "+temp.data);
        temp=temp.next;
      }
      Console.WriteLine();
    }
    else
    {
      Console.WriteLine("Empty Linked list"); 
    }
  }
  public void reverse_k(int k)
  {
    if(head==null || k<=1)
    {
      return;
    }
    Console.WriteLine("Reverse alternate "+k+" nodes");

    Node auxiliary=null,
    temp=head,
    back=null,
    current=head,
    root=head,
    first=null;
    int move=1, size=0;
    while(temp!=null)
    {
      size++;

      if(size==k)
      {

        if(move==1)
        {

          temp=temp.next;
          back=temp;
          root=current;

          if(current!=head)
          {
            current=current.next;
          }
          while(current != null && size > 0)
          {

            auxiliary = current.next;
            current.next = back;
            back = current;
            current = auxiliary;
            size--;
          }
          if(root==head)
          {
            head=back;
          }
          else
          {
            root.next=back;
          }
          move=0;
        }
        else
        {
          current=temp;
          temp=temp.next;
          move=1;
          size=0;
        } 
      }
      else
      {
        temp=temp.next;
      }
    }
  }

  public static void Main(String[] args) 
  {

    LinkedList obj = new LinkedList();
    //Insert element of linked list
    obj.insert(1);
    obj.insert(2);
    obj.insert(3);
    obj.insert(4);
    obj.insert(5);
    obj.insert(6);
    obj.insert(7);
    obj.insert(8);
    obj.insert(9);
    obj.insert(10);
    //display all node
    obj.display();

    int k=3;

    obj.reverse_k(k);
    //display all node
    obj.display();
  }
}

Output

Linked List Element :  1  2  3  4  5  6  7  8  9  10
Reverse alternate 3 nodes
Linked List Element :  3  2  1  4  5  6  9  8  7  10
<?php
//Php program 
//Reverse alternate K nodes in a Linked List
class Node
{
  public $data;
  public $next;
  function __construct($data)
  {
    $this->data = $data;
    $this->next = NULL;
  }
}
class LinkedList
{

  public $head;
  function __construct()
  {
    $head=NULL;
  }
  /*
  * Append the Given data value at end of linked list
  * Fun : insert
  * Parm: data value
  *@return None
  */
  function insert($data)
  {
    $newNode=new Node($data); 

    if($this->head==NULL)
    {
      $this->head=$newNode;
    }
    else
    {
      $temp=$this->head;

      //find last node of linked list
      while($temp->next!=NULL)
      {
        $temp=$temp->next;
      }
      //add new node to last of linked list
      $temp->next=$newNode;
    }
  }
  //Display all inserted node in linked list
  function display()
  {
    if($this->head==NULL)
    {
      echo "\nEmpty Linked List\n";
    }
    else
    {
      $temp=$this->head;
      echo "\nLinked List :";
      while($temp!=NULL)
      {
        //display node value
        echo "  ".$temp->data;
        $temp=$temp->next; //visit to next node
      }
    }   
  }
  function reverse_k($k)
  {
    if($this->head==NULL || $k<=1)
    {
      return;
    }
    echo "\nReverse alternate ".$k ." nodes";

    $auxiliary=NULL;
    $temp=$this->head;
    $back=NULL;
    $current=$this->head;
    $root=$this->head;
    $first=NULL;
    $move=1; 
    $size=0;
    while($temp!=NULL)
    {
      $size++;

      if($size==$k)
      {

       if($move==1)
       {

        $temp=$temp->next;
        $back=$temp;
        $root=$current;

        if($current != $this->head)
        {
          $current = $current->next;
        }
        while($current != NULL && $size > 0)
        {

          $auxiliary = $current->next;
          $current->next = $back;
          $back = $current;
          $current = $auxiliary;
          $size--;
        }
        if($root==$this->head)
        {
          $this->head=$back;
        }
        else
        {
          $root->next=$back;
        }
        $move=0;
      }
      else
      {
        $current=$temp;
        $temp=$temp->next;
        $move=1;
        $size=0;
      } 
    }
    else
    {
      $temp=$temp->next;
    }
  }
}
}
function main()
{
    //Make a object of LinkedList class
  $obj= new LinkedList();

    //insert element of linked list
  $obj->insert(1);
  $obj->insert(2);
  $obj->insert(3);
  $obj->insert(4);
  $obj->insert(5);
  $obj->insert(6);
  $obj->insert(7);
  $obj->insert(8);
  $obj->insert(9);
  $obj->insert(10);
    //display all node
  $obj->display();

  $k=3;

  $obj->reverse_k($k);


  $obj->display();
}
main();
?>

Output

Linked List :  1  2  3  4  5  6  7  8  9  10
Reverse alternate 3 nodes
Linked List :  3  2  1  4  5  6  9  8  7  10


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.

New Comment







© 2021, kalkicode.com, All rights reserved