Leetcode之PHP版题目解析（206. Reverse Linked List）

2019-4-1 星期一  开始吧

上一题链接 Leetcode之PHP版题目解析（204. Count Primes）

Github整理地址:https://github.com/wuqinqiang/leetcode-php

题目描述

反转单链表

题目分析

题目让我们用两种方式实现，一种迭代一种递归。先来迭代吧。比如说当前单链表是：

可以看出遍历链表的时候，只要吧当前节点的下一个指针指向更改为它的上一个节点，更改的时候需要用另一个指针来存储下一个节点。

/**
     * @param ListNode $head
     * @return ListNode
     */
    function reverseList($head) {
        $prev=null;
        $curr=$head;
        while($curr !==null){
            $nextcode=$curr->next;
            $curr->next=$prev;
            $prev=$curr;
            $curr=$nextcode;
        }
        return $prev;  
    }

解法二

递归，先来看下下面这段。

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