题目

反转一个单链表。

示例:

1 2	输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

Reverse a singly linked list.

Example:

1 2	Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

解题方法

迭代

题目要求使用迭代和递归两种方法，首先是迭代。迭代过程主要是用三个指针，next保留当前节点head的下一个节点，pre保留上一个节点，将head.next指向pre，然后pre指向head(head已经成为下一次迭代的pre)，head指向next。迭代到最后一个节点后，尾节点变为头节点，将head.next指向pre。这段代码跑了0ms，超过了100.00%的Java提交。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // Method_01  0ms  100.00%
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {  // 边界判断
            return head;
        }

        ListNode pre = null;
        ListNode next;
        while(head.next != null) {  // 迭代过程
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        head.next = pre;  // 处理尾节点

        return head;
    }
}

递归

递归如下，耗时耗空间，这段代码跑了1ms，超过了21.74%的Java提交。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // Method_02  1ms  21.74%
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode newListNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newListNode;
    }
}