1public class ReverseList {
 2
 3    private static class ListNode {
 4        int val;
 5        ListNode next;
 6
 7        ListNode() {
 8        }
 9
10        ListNode(int val) {
11            this.val = val;
12        }
13
14        ListNode(int val, ListNode next) {
15            this.val = val;
16            this.next = next;
17        }
18
19
20    }
21
22    /**
23     * 206. 反转链表
24     * 反转一个单链表。
25     * <p>
26     * 示例:
27     * <p>
28     * 输入: 1->2->3->4->5->NULL
29     * 输出: 5->4->3->2->1->NULL
30     * 进阶:
31     * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
32     *
33     * @param head
34     * @return
35     */
36
37    //迭代
38    public static ListNode reverseList(ListNode head) {
39        ListNode temp = null;
40        ListNode pre = null, curr = head;
41        while (curr != null) {
42            temp = curr.next;
43            curr.next = pre;
44            pre = curr;
45            curr = temp;
46        }
47        return pre;
48    }
49
50    //递归
51    public static ListNode reverseList1(ListNode head) {
52        return reverse(null, head);
53    }
54
55    private static ListNode reverse(ListNode pre, ListNode curr) {
56        if (curr == null) {
57            return pre;
58        }
59        ListNode temp = null;
60        temp = curr.next;
61        curr.next = pre;
62        pre = curr;
63        curr = temp;
64        return reverse(pre, curr);
65    }
66
67    public static void main(String[] args) {
68        ListNode l4 = new ListNode(4);
69        ListNode l3 = new ListNode(3, l4);
70        ListNode l2 = new ListNode(2, l3);
71        ListNode l1 = new ListNode(1, l2);
72//        reverseList(l1);
73        reverseList1(l1);
74    }
75}