Problem Description: https://www.hackerrank.com/challenges/reverse-a-doubly-linked-list/problem
Runtime complexity of my below code: O(n) where n is the size of the linked list.
Solution approach: Recursive
My Java Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*; public class Solution { static class DoublyLinkedListNode { public int data; public DoublyLinkedListNode next; public DoublyLinkedListNode prev; public DoublyLinkedListNode(int nodeData) { this.data = nodeData; this.next = null; this.prev = null; } } static class DoublyLinkedList { public DoublyLinkedListNode head; public DoublyLinkedListNode tail; public DoublyLinkedList() { this.head = null; this.tail = null; } public void insertNode(int nodeData) { DoublyLinkedListNode node = new DoublyLinkedListNode(nodeData); if (this.head == null) { this.head = node; } else { this.tail.next = node; node.prev = this.tail; } this.tail = node; } } public static void printDoublyLinkedList(DoublyLinkedListNode node, String sep, BufferedWriter bufferedWriter) throws IOException { while (node != null) { bufferedWriter.write(String.valueOf(node.data)); node = node.next; if (node != null) { bufferedWriter.write(sep); } } } // Complete the reverse function below. /* * For your reference: * * DoublyLinkedListNode { * int data; * DoublyLinkedListNode next; * DoublyLinkedListNode prev; * } * */ static DoublyLinkedListNode reverse(DoublyLinkedListNode head) { return reverseRecur(head, head.next); } private static DoublyLinkedListNode reverseRecur(DoublyLinkedListNode current, DoublyLinkedListNode nextNode) { // 2, 3 3, 4 4, \0 if (current == null) return current; if (nextNode == null && current.prev == null) { return current; } //Node nextNode = current.next; 2 DoublyLinkedListNode prevNode = current.prev; // \0 1 2 3 if (nextNode == null) { current.prev = null; return current; // 4 } //Assume reversed till current. DoublyLinkedListNode nextToNext = nextNode.next; // 4 \0 // 1 <-> 2 <-> 3 <-> 4 -> 4<->3<->2<->1 nextNode.next = current; //4 <-> 3 <-> 2 <-> 1 -> \0 current.prev = nextNode; current.next = prevNode; return reverseRecur(nextNode, nextToNext); // 3, 4 4, \0 } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int t = scanner.nextInt(); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); for (int tItr = 0; tItr < t; tItr++) { DoublyLinkedList llist = new DoublyLinkedList(); int llistCount = scanner.nextInt(); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); for (int i = 0; i < llistCount; i++) { int llistItem = scanner.nextInt(); scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?"); llist.insertNode(llistItem); } DoublyLinkedListNode llist1 = reverse(llist.head); printDoublyLinkedList(llist1, " ", bufferedWriter); bufferedWriter.newLine(); } bufferedWriter.close(); scanner.close(); } } |
Do share your thoughts below!
Until next time, Happy Coding!
