1、背景

最近在學(xué)習(xí)王爭老師的數(shù)據(jù)結(jié)構(gòu)與算法之美,自己將課程中涉及的算法用PHP的形式表達(dá)出來,程序?qū)懙挠袉栴},歡迎留言溝通哦

2、單鏈表判斷回文字符串原理

核心（通過快慢指針定位中間節(jié)點(diǎn)），步驟，定義反轉(zhuǎn)鏈表，快慢指針， 慢指針每次前進(jìn)一步，快指針每次前進(jìn)兩步，到達(dá)中間位置后，慢指針與反轉(zhuǎn)鏈表對(duì)比，如果完全相等，則是回文字符串。

3、操作

PHP實(shí)現(xiàn)代碼

//單鏈表
class LinkedList{
    public $val;
    public $next;
    public function __construct($val)
    {
        $this->val = $val;
    }
}


class Test{
    public function isPalindromeStr(LinkedList $linkedList){
        if($linkedList == null || $linkedList->next == null){
            return true;
        }
        $strRev = null;//反轉(zhuǎn)鏈表
        $slow = $linkedList;//慢指針
        $fast = $linkedList;//快指針
        //快指針跑完鏈表跳出循環(huán)
        while ($fast != null && $fast->next != null){
            $fast = $fast->next->next;
            //慢指針數(shù)據(jù)反轉(zhuǎn)
            $next = $slow->next;
            $slow->next = $strRev;
            $strRev = $slow;
            $slow = $next;
        }
        //當(dāng)鏈表數(shù)據(jù)為奇數(shù)時(shí)的判斷
        if($fast != null){
            $slow = $slow->next;
        }
       //慢指針和反轉(zhuǎn)鏈表進(jìn)行判斷
        while ($slow != null){
            if($slow != $strRev){
                return false;
            }
            $slow = $slow->next;
            $strRev = $strRev->next;
        }

        return true;

    }
}

$linkedList[0] = new LinkedList(1);
$linkedList[1] = new LinkedList(2);
$linkedList[2] = new LinkedList(3);
$linkedList[3] = new LinkedList(3);
$linkedList[4] = new LinkedList(2);
$linkedList[5] = new LinkedList(1);

$linkedList[0]->next = $linkedList[1];
$linkedList[1]->next = $linkedList[2];
$linkedList[2]->next = $linkedList[3];
$linkedList[3]->next = $linkedList[4];
$linkedList[4]->next = $linkedList[5];

$test = new Test();

var_dump($test->isPalindromeStr($linkedList[0]));

4、源碼地址

https://gitee.com/ERWTWERWERWERWER/simple_small_algorithm/blob/master/algorithm/PalindromeString.php