Reverse Linked List from position m to n

Write a program to Reverse Linked List from position m to n

Example 1:

Input: 1->2->3->4->5->6->7->NULL, n = 2, m = 4
Output: 1->4->3->2->5->6->7->NULL

Approach:

Java

public class LinkListReverseFromNtoM {
    public static void main(String[] args) {
        ListNode l = new ListNode(1);
        l.next = new ListNode(2);
        l.next.next = new ListNode(3);
        l.next.next.next = new ListNode(4);
        l.next.next.next.next = new ListNode(5);
        int n = 2;
        int m = 4;
        ListNode node = reverseListNtoM(l, n, m);
        // print linklist
        linkedListTraversal(node);
    }

// method used for print
    private static void linkedListTraversal(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

    // method to reverse list from n to m
    public static ListNode reverseListNtoM(ListNode head,
                         int n, int m) {
        // Base condition
        if (head == null || n == m || head.next == null)
            return head;

        int count = 0;

        // varible to hold the previous of n
        // mth node and the nth node
        ListNode temp = head;
        ListNode prevN = head;
        ListNode nthNode = head;

        // iterate till the end of list
        while (temp != null) {
            // increment the count
            count++;

            // if count is less than n then
            // update previous of n
            if (count < n) {
                prevN = temp;
            }

            // if count is same as n
            // then update nthNode
            if (count == n) {
                nthNode = temp;
            }
               temp = temp.next;

            // if count is same as
            // m then break out of loop
            if (count == m) {
                break;
            }
       
        }

        // now varible for reverse
        ListNode reverse = null;
        ListNode curr = nthNode;
        ListNode curr1 = nthNode;
        ListNode first = nthNode;

        // iterate tiil curr is not
        // eqaul to temp
        while (curr != temp) {
            curr = curr.next;
            curr1.next = reverse;
            reverse = curr1;
            curr1 = curr;
        }

        // update the pointers in new list
        prevN.next = reverse;
        first.next = temp;

        // if n is 1 then
        // new head will we the reverse
        if (n == 1)
            head = reverse;

        // return the head
        return head;

    }
}

class ListNode {

    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
// Time Complexity : O(n)

C++

#include <bits/stdc++.h>
using namespace std;
//Struture of  node
struct Node
{ 
   int data;
   Node *next;
   Node(int data)
    {
        this->data=data;
        this->next=NULL;
    }
};
//function to reverse nodes from
//n to m
Node *reverseFromNToM(Node *head,int n,int m)
{

    //if list is empty or n==m
    //then return the original list
    if(head==NULL||n==m)
      return head;

    //varibale to hold the count
    //of nodes
    int count=0;

    //varible to hold the previous of n
    //mth node and the nth node
    Node *temp=head,*prevN=head,*nthNode=head,*mthNode=head;

    //iterate till the end of list 
    while(temp!=NULL)
     {
        //increment the count
         count++;
    
      //if count is less than n then
      //update previous of n
       if(count<n)
        {
            prevN=temp;
        }

        //if count is same as n
        //then update nthNode
      if(count==n)
       {
           nthNode=temp;
       }

       //if count is same as
       //m then update mthNode
       //and break out of loop
      if(count==m)
        {
            mthNode=temp;

            //temp store the next of mthNode
            temp=temp->next;
            break;
        }
        temp=temp->next;
        
     }

     //now varible for reverse
    Node *reverse=NULL,*curr=nthNode,*curr1=nthNode,*first=nthNode;

    //iterae tiil curr is not 
    //eqaul to temp
    while(curr!=temp)
      {
        curr=curr->next;
        curr1->next=reverse;
        reverse=curr1;
        curr1=curr;
      }

    //update the pointers in new list
    prevN->next=reverse;
    first->next=temp;

    //if n is 1 then
    //new head will we the reverse
    if(n==1)
      head=reverse;

    //return the head
    return head;
}
int main()
{
  Node *head=new Node(1);
  head->next=new Node(2);
  head->next->next=new Node(3);
  head->next->next->next=new Node(4);
  head->next->next->next->next=new Node(5);
  head->next->next->next->next->next=new Node(6);
   head->next->next->next->next->next->next=new Node(7);
  int n=2,m=4;

  head=reverseFromNToM(head,n,m);
  Node *temp=head;
  cout<<"New List is\n";
  while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    return 0;
}
//Time Complexity: O(n)
//Space Complexity:O(1)