题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

1 -> 2 -> 3 -> 4 -> 5

V

5 -> 4 -> 3 -> 2 -> 1

输入：head = [1,2,3,4,5]

输出：[5,4,3,2,1]

示例 2：

1 -> 2

V

2 -> 1

输入：head = [1,2]

输出：[2,1]

提示：

链表中节点的数目范围是 [0, 5000]

-5000 <= Node.val <= 5000

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reverse-linked-list

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答一

这道题倒是比较简单。

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function reverseList($head) {
        if ($head->next === null) {
            return $head;
        }

        $p1 = $head;
        $p2 = null;

        $head = new ListNode();

        while ($p1) {
            $p2 = $p1->next;
            $p1->next = $head->next;
            $head->next = $p1;
            $p1 = $p2;
        }

        return $head->next;
    }
}

执行用时：8 ms, 在所有 PHP 提交中击败了64.32%的用户

内存消耗：20.2 MB, 在所有 PHP 提交中击败了29.46%的用户

通过测试用例：28 / 28

解答二

少一个最前边的节点判断看会不会快一点。

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function reverseList($head) {
        $p1 = $head;
        $p2 = null;

        $head = new ListNode();

        while ($p1) {
            $p2 = $p1->next;
            $p1->next = $head->next;
            $head->next = $p1;
            $p1 = $p2;
        }

        return $head->next;
    }
}

执行用时：8 ms, 在所有 PHP 提交中击败了64.32%的用户

内存消耗：19.9 MB, 在所有 PHP 提交中击败了57.68%的用户

通过测试用例：28 / 28

速度没变，但是内存使用降下来了。

解答三 ✅

取消空的头节点的创建，让内存消耗再小一点。

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function reverseList($head) {
        $p1 = $head;
        $p2 = $head = null;

        while ($p1) {
            $p2 = $p1->next;
            $p1->next = $head;
            $head = $p1;
            $p1 = $p2;
        }

        return $head;
    }
}

执行用时：8 ms, 在所有 PHP 提交中击败了64.32%的用户

内存消耗：19.8 MB, 在所有 PHP 提交中击败了80.91%的用户

通过测试用例：28 / 28