sub list of a sorted (ascending order)link list is reversed. correct it.

Input
1->2->3->4->8->7->6->5->9->10->11
Output
1->2->3->4->5->6->7->8->9->10->11

To solve this problem :

  1. Find the pointer, from dis order starts say first
  2. Find the pointer where dis order ends say last node
  3. Setting next of last node to null
  4. Reverse the linked list from first to last
  5. join the linked list with reversed linked list
  6. join the linked list with remaining list

Node Class : Used for Creating Link List

public class Node<T>
  {
    private T nodeValue;
    private Node<T> nextNode;

    public Node()
    {
      this.nodeValue = default(T);
      this.nextNode = null;
    }

    public Node(T nodeValue)
    {
      this.nodeValue = nodeValue;
      this.nextNode = null;
    }

    /// <summary>
    /// Value of node
    /// </summary>
    public T NodeValue
    {
      get { return nodeValue; }
      set { this.nodeValue = value; }
    }

    /// <summary>
    /// The node this node links to
    /// </summary>
    public Node<T> NextNode
    {
      get { return this.nextNode; }
      set { this.nextNode = value; }
    }
  }
    /// <summary>
    /// 1--->2--->3--->4--->9--->8-->7--->6--->5--->10--->11--->NULL
    /// </summary>
    /// <param name="head"></param>
    public static void correctList(Node<int> head)
    {

      if (head == null)
      {
        Console.WriteLine("Empty List");
        return;
      }

      Node<int> current = head;
      Node<int> first = null;
      Node<int> last = null;
      Node<int> mark1 = null;

      while (current != null && current.NodeValue < current.NextNode.NodeValue)
      {
        mark1 = current;
        current = current.NextNode;
      }

      first = current; //Pointer to node, LL Disorder starts

      while (current != null && current.NodeValue > current.NextNode.NodeValue)
        current = current.NextNode;


      last = current.NextNode; //Pointer to node, LL Disorder Ends

      current.NextNode = null; // Setting next of last node to null

      Reverse(ref first);//reverse the sub list that dis order starts to disorder ends

      mark1.NextNode = first; // join the initial linklist with reversed linkedlist 

      while (first.NextNode != null)
      {
        first = first.NextNode;
      }

      first.NextNode = last; // join the merged link list with sorted linklist
      Console.WriteLine();
      Console.WriteLine("Output");
      
      PrintList(head);
      Console.WriteLine();

    }

    public static void Reverse(ref Node<int> head)
    {

      Node<int> first;
      Node<int> rest;
      if (head == null) return;
      first = head;
      rest = first.NextNode;
      if (rest == null) return;
      Reverse(ref rest);
      first.NextNode.NextNode = first;
      first.NextNode = null;
      head = rest;

    }
    public static void PrintList(Node<int> head)
    {
      while (head != null)
      {
        Console.Write(head.NodeValue);
        head = head.NextNode;
        if (head != null) Console.Write("->");
      }

    }

Main Program

      Node<int> a = new Node<int>(1);
      Node<int> a1 = new Node<int>(2);
      Node<int> a2 = new Node<int>(3);
      Node<int> a3 = new Node<int>(4);
      Node<int> a4 = new Node<int>(8);
      Node<int> a5 = new Node<int>(7);
      Node<int> a6 = new Node<int>(6);
      Node<int> a7 = new Node<int>(5);
      Node<int> a8 = new Node<int>(9);
      Node<int> a9 = new Node<int>(10);
      Node<int> a10 = new Node<int>(11);

      a.NextNode = a1;
      a1.NextNode = a2;
      
      a2.NextNode = a3;
      
      a3.NextNode = a4;
      
      a4.NextNode = a5;
      
      a5.NextNode = a6;
      
      a6.NextNode = a7;
      
      a7.NextNode = a8;
      
      a8.NextNode = a9;

      a9.NextNode = a10;
      
      a10.NextNode = null;
      Console.WriteLine("Input");
      Microsoft.PrintList(a);
      Microsoft.correctList(a);