[第 5 天] 4.20 (万向链表)

1.回文链表

1.1题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

• 示例一：

输入：head = [1,2,2,1]
输出：true

• 示例二：

输入：head = [1,2]
输出：false

1.2解法：双指针

1.2.1解法思路

• 使用快慢指针遍历整个链表，以此找到链表的中间节点；
• 并在遍历过程中，反转slow遍历过的每个节点，用cur标记；
• 遍历的终止条件为 fast指向的节点为空 或者 fast指向的节点的下一个节点为空

1.2.2代码实现

	public boolean isPalindrome(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        ListNode cur=null;  //反转链表
        
        //1、找到中间节点
        while(fast!=null && fast.next!=null){
            ListNode tmp=slow;      //暂存slow节点
            fast=fast.next.next;
            slow=slow.next;

            tmp.next=cur;   //反转
            cur=tmp;        //更新cur节点
        }

        //2、判断链表长度是否为奇数：若为奇数，则将slow移动到下一位
        if(fast!=null){
            slow=slow.next;
        }

        //3、遍历后半段的回文串和前半段的回文串
        while(slow!=null && cur!=null){
            if(slow.val!=cur.val){
                return false;
            }
            slow=slow.next;
            cur=cur.next;
        }
        return true;
    }