Problem:
* Given a node from a cyclic linked list which has been sorted,
* write a function to insert a value into the list such that it remains a cyclic sorted list.
* The given node can be any single node in the list.
Solution:
Source Code:
/** * Given a node from a cyclic linked list which has been sorted, * write a function to insert a value into the list such that it remains a cyclic sorted list. * The given node can be any single node in the list. */ /** * @author Antonio081014 * @since Oct 28, 2013, 10:43:52 AM */ public class Test { public static void main(String[] args) { CycledList list = new CycledList(); list.print(); list.insert(3); list.print(); list.insert(1); list.insert(1); list.print(); } } class CycledList { public Node head; /** * Several Cases: * 1st, when linked list is empty; * 2nd, when new element is either minimum or maximum; * 3rd, when new element is in between two sorted elements. * * * Since this list is like a circle, we don't necessary to have the smallest * element as the head, but it's definitely sorted. * */ public void insert(int x) { // 1st Case; if (head == null) { head = new Node(x); head.next = head; return; } Node p = head; Node prev = null; do { prev = p; p = p.next; // 2nd Case; if (prev.data >= p.data && (x <= p.data || x >= prev.data)) break; // 3rd Case; if (prev.data <= x && p.data >= x) break; } while (p != head); Node tmp = new Node(x); prev.next = tmp; tmp.next = p; } public void print() { if (head == null) { System.out.println("Empty Cycled List"); return; } Node p = head; do { System.out.print(p.data + " "); p = p.next; } while (head != p); System.out.println(); } } class Node { public int data; public Node next; public Node(int x) { this.data = x; next = null; } public Node(int x, Node n) { this.data = x; this.next = n; } }
No comments :
Post a Comment