package leetcode;

import java.util.Stack;

/**
 * https://leetcode.com/problems/reverse-linked-list/
 */
public class Problem206 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public ListNode reverseList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        for (ListNode node = head; node != null; node = node.next) {
            stack.push(node);
        }
        ListNode n1 = null;
        ListNode n2 = null;
        ListNode newHead = null;
        while (!stack.isEmpty()) {
            n1 = stack.pop();
            if (newHead == null) {
                newHead = n1;
            }
            if (stack.isEmpty()) {
                break;
            }
            n2 = stack.pop();
            n1.next = n2;
            n2.next = null;
            stack.push(n2);
        }
        return newHead;
    }
}

@@ -16,33 +16,8 @@
 e;%0A%0A
-import java.util.Stack;%0A%0A
 /**%0A
@@ -301,22 +301,16 @@
     
-Stack%3C
 ListNode
 %3E st
@@ -309,197 +309,135 @@
 Node
-%3E stack = new Stack%3C%3E();%0A        for (ListNode node = head; node != null; node = node.next) %7B%0A            stack.push(node);%0A        %7D%0A        ListNode n1 = null;%0A        ListNode n2 = null;
+Ref ref = new ListNodeRef();%0A        reverse(head, ref);%0A        return ref.head;%0A    %7D%0A%0A    private static class ListNodeRef %7B
 %0A   
@@ -433,32 +433,40 @@
 deRef %7B%0A        
+private 
 ListNode newHead
@@ -462,93 +462,91 @@
 ode 
-newHead = null
+head
 ;%0A    
+%7D%0A%0A
     
-while (!stack.isEmpty()) %7B%0A            n1 = stack.pop();%0A    
+private static ListNode reverse(ListNode head, ListNodeRef ref) %7B%0A
     
@@ -553,20 +553,17 @@
     if (
-newH
+h
 ead == n
@@ -585,140 +585,121 @@
     
-    newHead = n1;%0A            %7D%0A            if (stack.isEmpty()) %7B%0A                break;%0A            %7D%0A            n2 = stack.pop()
+return null;%0A        %7D%0A        ListNode next = head.next;%0A        if (next == null) %7B%0A            ref.head = head
 ;%0A  
@@ -712,20 +712,19 @@
     
-n1.next = n2
+return head
 ;%0A  
@@ -733,14 +733,22 @@
     
+%7D%0A
     
-n2
+    head
 .nex
@@ -769,37 +769,69 @@
     
-    stack.push(n2);%0A        %7D
+ListNode node = reverse(next, ref);%0A        node.next = head;
 %0A   
@@ -846,12 +846,9 @@
 urn 
-newH
+h
 ead;

Update problem 206