Leetcode之PHP版题目解析(206. Reverse Linked List)


2019-4-1 星期一  开始吧

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


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

fc60a954efc55b266f51a52fbb033b1c.png


反转单链表

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

66453abfff62dfaf0e6fe6de311e43fd.png

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

/**
     * @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;  
    }

解法二

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

98d376cbd2b7bd47ab34f375100d3ad0.png

 /**
     * @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;
    }

Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D21 344. Reverse String

>> 下一篇: Leetcode PHP题解--D22 806. Number of Lines To Write String