题解 | #判断一个链表是否为回文结构#
判断一个链表是否为回文结构
http://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
判断一个链表是否为回文结构
1、题意重述
给定一个链表，请判断该链表是否为回文结构。 回文是指该字符串正序逆序完全一致。
换句话说，就是判断链表倒序以后，然后和原来的链表是否相等。
2、思路整理
使用双指针的思想：
Step1:使用两个指针fast和slow，fast每次走两步，slow每次走一步。
Step2：当fast的指向为空时，记录slow的位置。
Step3：将slow以后的部分进行翻转，并且与之前的部分进行比较。如果相等，则是回文结构，否则不是回文结构。
3、代码实现
public boolean isPail(ListNode head) {
ListNode fast = head, slow = head;
//通过快慢指针找到中点
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) {
slow = slow.next;
}
slow = reverse(slow); //翻转后半部分
fast = head;
while (slow != null) {
//比较节点值是否相等
if (fast.val != slow.val)
return false;
fast = fast.next;
slow = slow.next;
}
return true;
}
//反转链表
public ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
4、复杂度分析
时间复杂度：一层循环，因此时间复杂度为。
空间复杂度：使用常数级内存地址空间，因此空间复杂度为。
22年春节特别专栏_双指针 文章被收录于专栏
双指针题解，图片随便找的！
⑨✌们拿它练练面试愣是给他整出幻觉了
