【力扣 Hot100 | 第五天】4.20（回文链表）

本文主要是介绍【力扣 Hot100 | 第五天】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;}

这篇关于【力扣 Hot100 | 第五天】4.20（回文链表）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---