php 实现链表的反转--迭代和递归

1. 递归：思路说明请看 代码注释

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

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function reverseList($head) {
        if ($head == null || $head->next == null) {
            return $head;
        }
        // 由于是对象，所以存在值引用
        // 即：head的变化会影响到 tmp
        $tmp = $this->reverseList($head->next);
        // 1->2->3->4->5
        // 当 $head = 4， $head->next->next = null
        // $head->next->next = $head; 5->4
        $head->next->next = $head;
        // $head->next = null, 
        $head->next = null;
        return $tmp;
    }
}

2. 迭代：使用 pre 代表遍历过的节点、cur 表示当前正在遍历的节点

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

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