Reverse Linked List

1package pkg5leetcode;2 3/*4 * LeetCode 206: Reverse Linked List  (Easy)5 * -----------------------------------------6 * Reverse a singly linked list. Shown iteratively and recursively.7 *8 * COMPLEXITY: Time O(n); iterative Space O(1), recursive Space O(n) (call stack).9 */10public class leetcode9ReverseLinkedList {11 12    static class ListNode {13        int val; ListNode next;14        ListNode(int val) { this.val = val; }15    }16 17    static ListNode reverseIterative(ListNode head) {18        ListNode prev = null;19        while (head != null) {20            ListNode next = head.next;21            head.next = prev;22            prev = head;23            head = next;24        }25        return prev;26    }27 28    static ListNode reverseRecursive(ListNode head) {29        if (head == null || head.next == null) return head;30        ListNode newHead = reverseRecursive(head.next);31        head.next.next = head;32        head.next = null;33        return newHead;34    }35 36    static ListNode build(int... vals) {37        ListNode dummy = new ListNode(0), tail = dummy;38        for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; }39        return dummy.next;40    }41    static int[] toArray(ListNode head) {42        java.util.List<Integer> out = new java.util.ArrayList<>();43        for (ListNode c = head; c != null; c = c.next) out.add(c.val);44        return out.stream().mapToInt(Integer::intValue).toArray();45    }46 47    public static void main(String[] args) {48        check(java.util.Arrays.equals(toArray(reverseIterative(build(1, 2, 3, 4, 5))), new int[]{5, 4, 3, 2, 1}), "iterative");49        check(java.util.Arrays.equals(toArray(reverseRecursive(build(1, 2, 3))), new int[]{3, 2, 1}), "recursive");50        check(toArray(reverseIterative(build())).length == 0, "empty");51        System.out.println("leetcode9ReverseLinkedList: all tests passed");52    }53 54    static void check(boolean cond, String name) {55        if (!cond) throw new AssertionError("FAILED: " + name);56        System.out.println("  PASS " + name);57    }58}