206. 反转链表 2种方法-迭代和递归

思路：

递归：

    递归的方式就是不断调用自己本身（需要注意的是必须设置停止递归的条件）。

既然调用一次方法的结果是列表已经反转，那么就一层一层往下调用，即不断将给定节点的下一个节点反转而得到一个反转后的新的头结点；然后一层一层进去达到原列表的最后一个元素，方法的返回值即反转后新列表的第一个元素，然后再一层一层返回串起来成为新列表。

迭代：

    迭代的方式是利用一个while循环，从给定列表的头结点开始让其成为新列表的最后一个节点，一直操作到原列表的最后一个元素。

代码：

public class _002_206_反转链表 {


    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public ListNode reverseList(ListNode head) {
//        return reverseList_递归(head);
        return reverseList_迭代(head);
    }

    /**
     * 迭代
     */
    public ListNode reverseList_迭代(ListNode head) {
        if (head == null || head.next == null) { return head; }

        ListNode theHead = head;
        ListNode newHead = null;
        ListNode tmp = null;
        while (theHead != null) {
            tmp = theHead.next;
            theHead.next = newHead;
            newHead = theHead;
            theHead = tmp;
        }
        return newHead;
    }

    /**
     * 递归
     */
    public ListNode reverseList_递归(ListNode head) {
        if (head == null || head.next == null) { return head; }

        // 反转好的新列表的头结点
        ListNode newHead = reverseList(head.next);
        /*
        找到新列表的最后一个元素，也就是原列表head.next元素；
        在将来新列表中，这个元素的下一个元素是head；
         */
        head.next.next = head;
        head.next = null;

        return newHead;
    }

    public static void main(String args[]) {
        System.out.println("Hellow world!");

        ListNode head = new ListNode(1);
        ArrayList<ListNode> list = new ArrayList<>();
        list.add(head);

        for (int i = 1; i <= 5; i++) {
            ListNode node = new ListNode(i+1);
            list.add(node);

            list.get(i - 1).next = node;
        }

        System.out.println(list);



        ListNode revHead = new _002_206_反转链表().reverseList(head);
        System.out.println(revHead.val);
        printList(revHead);

        System.out.println(">>>>>end");
    }


    private static void printList(ListNode head) {
        StringBuilder str = new StringBuilder();
        str.append("【list: ");

        if (head == null) {
            str.append("null】").toString();
            System.out.println(str);
            return;
        }
        str.append(head.val);
        ListNode node = head.next;

        while(node != null) {
            str.append(", " + node.val);
            node = node.next;
        }
        str.append("】");

        System.out.println(str.toString());
    }

}

原题：

/*
206. 反转链表
https://leetcode-cn.com/problems/reverse-linked-list/


反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 */