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 :
- Find the pointer, from dis order starts say first
- Find the pointer where dis order ends say last node
- Setting next of last node to null
- Reverse the linked list from first to last
- join the linked list with reversed linked list
- 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);
Filed under:
Code
Leave a comment