剑指offer（十五）反转链表

点击进入 牛客网题库：反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

上来，想了10分钟，然后就撸了一个

   /**
     * 时间复杂度 O(n) 
     * 空间复杂度 O(n)
     * @param head
     * @return
     */
 public ListNode ReverseList(ListNode head) {
        final ArrayList<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(0, head);
            head = head.next;
        }

        final int size = list.size();
        ListNode tmpNode = list.get(0);
        for (int i = 1; i < size; i++) {
            tmpNode.next = list.get(i);
            tmpNode = tmpNode.next;
        }
        //一定要置为null，不然不通过，就相当于没有反转成功
        list.get(size -1).next = null;
        return list.get(0);
    }

对链表的恐惧，可想而知

方法二

    public ListNode ReverseList(ListNode head) {
        ListNode next = null;
        ListNode pre = null;

        ListNode lastHead = head;

        while(lastHead != null) {
            next = lastHead.next;
            lastHead.next = pre;

            pre = lastHead;
            lastHead = next;
        }
        return pre;
    }