Reverse the LinkedList
This is the algorithm to reverse the linked list.
This is how recursive technique works
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 |
package com.omt.learn.algo; public class ReverseTheLinkedList { public static void main(String args[]) { ListNode ln = createListNode("2->4->3->10->7"); ListNode reversed = reverseTheListByWhileLoop(ln); while (reversed != null) { System.out.print(reversed.val + "->"); reversed = reversed.next; } ln = createListNode("2->4->3->10->7->12->17"); reversed = reverseTheLinkedListRecursive(ln); System.out.println("\n--------------"); while (reversed != null) { System.out.print(reversed.val + "->"); reversed = reversed.next; } } public static ListNode reverseTheLinkedListRecursive(ListNode head) { if (head.next == null) { return head; } ListNode lastNode = reverseTheLinkedListRecursive(head.next); head.next.next = head; head.next = null; return lastNode; } public static ListNode reverseTheListByWhileLoop(ListNode head) { ListNode current = head; ListNode previous = null; while (current != null) { ListNode temp = current.next; current.next = previous; previous = current; current = temp; } return previous; } private static ListNode createListNode(String data) { String[] array = data.split("->"); ListNode listNode = null; for (String digit : array) { if (listNode == null) { listNode = new ListNode(Integer.parseInt(digit.trim())); } else { ListNode lastOne = listNode; while (lastOne.next != null) { lastOne = lastOne.next; } lastOne.next = new ListNode(Integer.parseInt(digit.trim())); } } return listNode; } } |