力扣官方给的代码中,这一步为什么是firstHalfNode.next,我觉得应该是firstHalfNode就行了,因为链表反转后得到的结点就是firstHalfNode哇。
题目:面试题 02.06. 回文链表
代码:
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// 还原链表并返回结果
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
不管逻辑是怎么样的,都不可以返回给firstHalfNode,因为这是个局部变量指针,改变它并不会改变原链表,你返回给它没有意义呀
如果你确实需要返回给它,那也应该是先找到它的上一级节点,然后将上一级节点的.next赋值
指针就类似一个写着字的小纸条,它上面的是邮寄地址
根据地址去邮寄才是应该做的事情,而改写小纸条上的字本身没有意义
首先,回文链表是指正向和反向遍历两个方向结果相同的链表。
对于力扣官方给出的回文链表题,需要判断一个链表是否为回文链表。考虑使用双指针法和链表反转来解决该问题。
具体步骤如下:
slow
和 fast
,分别指向链表的头结点。prev
、curr
和 next
来反转链表。firstHalfNode
,用于保存反转前的链表的头结点。代码如下:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
# 定义双指针
slow = fast = head
# 找到链表的中间结点
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# 反转链表的后半部分
prev = None
curr = slow
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
# 比较前半部分和后半部分是否相同
firstHalfNode = head
while prev:
if prev.val != firstHalfNode.val:
return False
prev = prev.next
firstHalfNode = firstHalfNode.next
return True
代码中的 firstHalfNode.next
是用来保存反转前的链表的头结点。经过反转后,prev
指向链表的末尾结点,该结点就是反转后的头结点,即 firstHalfNode
。由于 firstHalfNode
的值不能改变,所以需要用 firstHalfNode.next
来保存它的初始值,即反转前的头结点。