We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Inserting a Node Into a Sorted Doubly Linked List
Inserting a Node Into a Sorted Doubly Linked List
calvin_cheng_cc + 0 comments This worked for me (Java):
Node SortedInsert(Node head,int data) { Node n = new Node(); n.data = data; if (head == null) { return n; } else if (data <= head.data) { n.next = head; head.prev = n; return n; } else { Node rest = SortedInsert(head.next, data); head.next = rest; rest.prev = head; return head; } }
chetangautam + 0 comments This is wrong. Why do I see input as unsorted, when the problem mentions sorted.
RodneyShag + 0 comments Java Iterative solution - passes 100% of test cases
From my HackerRank solutions.
Runtime: O(n)
Space Complexity: O(1)Node SortedInsert(Node head, int data) { /* Create Node to insert */ Node newNode = new Node(); newNode.data = data; if (head == null) { // insert in empty list return newNode; } else if (data < head.data) { // insert in front of list newNode.next = head; head.prev = newNode; return newNode; } else { /* Walk list with 2 pointers */ Node n1 = null; Node n2 = head; while (n2 != null && n2.data < data) { n1 = n2; n2 = n2.next; } if (n2 == null) { // insert at end of list n1.next = newNode; newNode.prev = n1; } else { // insert in empty list n1.next = newNode; n2.prev = newNode; newNode.prev = n1; newNode.next = n2; } return head; } }
Let me know if you have any questions.
charanacharyah + 0 comments Looks like there's an issue with the Java version. I submitted this,
Node newNode = new Node(); newNode.data = data; if(head == null || head.data >= data){ newNode.next = head; newNode.prev = null; return newNode; } Node current = head; Node prev = null; while(current != null && current.data < data){ prev = current; current = current.next; } Node next = prev.next; newNode.prev = prev; newNode.next = next; if(next != null){ next.prev = newNode; } return head;
and I see that the condition head == null is never satisfied. Can someone help?
talsa + 0 comments static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode head, int data) { if (head == null) return new DoublyLinkedListNode(data); if(head.data > data) { DoublyLinkedListNode node = new DoublyLinkedListNode(data); node.next = head; return node; } head.next = sortedInsert(head.next, data); return head; }
Load more conversations
Sort 783 Discussions, By:
Please Login in order to post a comment