札记之PHP实现判断单链表是否为回文链表

回文示例：A -> B -> C -> C -> B -> A

思路

• 使用快慢指针获取中间节点
• 中间后部分进行反转
• 以后半部分为基准进行遍历来比较，例如在链表长度位偶数的情况下：
  A -> B -> C -> C -> B -> A 反转得到 A -> B -> C -> C <- B <- A，以前半部分为基准的话，会出现 null指针的异常。

代码实现：

class ListNode
{
    private $data;
    private $next;
    public function __construct(string $data)
    {
        $this->data = $data;
    }
    public function __get($var)
    {
        return $this->$var;
    }
    public function __set($var, $val)
    {
        return $this->$var = $val;
    }
}

class LinkedList
{
    private $head = NULL;
    private $length = 0;
    private $currentNode;

    public function getList()
    {
        return $this->head;
    }

    public function setList($head)
    {
        $this->head = $head;
    }
    
    public function insert(string $data = NULL)
    {
        $newNode = new ListNode($data);
        if ($this->head === NULL) {
            $this->head = &$newNode;
        } else {
            $currentNode = $this->head;
            while ($currentNode->next !== NULL) {
                $currentNode = $currentNode->next;
            }
            $currentNode->next = $newNode;
        }
        $this->length++;
        return true;
    }

    public function ispalindrome()
    {
        if ($this->head == NULL || $this->head->next == NULL) {
            return false;
        }  
        $midNode = $this->findMidNode();
        $newNode = $this->reverse($midNode);

        //逐个比较
        $p1 = $this->head;
        $p2 = $newNode;

        while ($p1 != NULL && $p2 != NULL && $p1->data == $p2->data) {
            $p1 = $p1->next;
            $p2 = $p2->next;
        }
        
        return $p2 == NULL;
    }

    public function findMidNode()
    {
        if ($this->head == NULL || $this->head->next == NULL) {
            return false;
        }

        $slow = $this->head;
        $fast = $this->head;

        while ($fast != NULL && $fast->next != NULL) {
            $fast = $fast->next->next;
            $slow = $slow->next;
        }
        return $slow;
    }

    public function reverse($head)
    {
        if ($head == null || $head->next == null) {
            return $head;
        }

        $reverseList = NULL;
        $next = NULL;

        while ($head !== NULL) {
            $next = $head->next;//保存后面链表数据

            $head->next = $reverseList;//将当前节点的下一节点置为前节点  
            $reverseList = $head;//将当前节点保存为前一节点

            $head = $next;//将当前节点置为下一节点
        }
        return $reverseList;
    }

    public function display()
    {
        echo 'LinkList length: ' . $this->length . PHP_EOL;
        $currentNode = $this->head;
        while ($currentNode !== NULL) {
            echo $currentNode->data . PHP_EOL;
            $currentNode = $currentNode->next;
        }
    }
}

$list = new LinkedList();
$list->insert(1);
$list->insert(2);
$list->insert(3);
$list->insert(3);
$list->insert(2);
$list->insert(1);

$list->display();
var_dump($list->ispalindrome());

运行结果

LinkList length: 6
1
2
3
3
2
1
midNode:
ListNode Object
(
    [data:ListNode:private] => 1
    [next:ListNode:private] => ListNode Object
        (
            [data:ListNode:private] => 2
            [next:ListNode:private] => ListNode Object
                (
                    [data:ListNode:private] => 3
                    [next:ListNode:private] => ListNode Object
                        (
                            [data:ListNode:private] => 3
                            [next:ListNode:private] => 
                        )

                )

        )

)
newNode:
ListNode Object
(
    [data:ListNode:private] => 1
    [next:ListNode:private] => ListNode Object
        (
            [data:ListNode:private] => 2
            [next:ListNode:private] => ListNode Object
                (
                    [data:ListNode:private] => 3
                    [next:ListNode:private] => 
                )

        )

)
/Users/jiayuan/tree/isPalindrome.php:129:
bool(true)