旧电脑怎么做网站,河南郑州最新事件,网站建设结论与改进,下载源代码的网站回文链表
题目描述#xff1a; 给你一个单链表的头节点 head #xff0c;请你判断该链表是否为回文链表。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
示例 1#xff1a;
输入#xff1a;head [1,2,2,1]
输出#xff1a;true示例 2#…回文链表
题目描述 给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。
示例 1
输入head [1,2,2,1]
输出true示例 2
输入head [1,2]
输出false提示
链表中节点数目在范围[1, 105] 内0 Node.val 9
进阶你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题
方法一思路分析
反转链表的一半 使用快慢指针找到链表的中点快指针每次移动两步慢指针每次移动一步当快指针到达链表末尾时慢指针就位于链表的中点对于奇数个节点的链表慢指针位于中间两个节点的第一个。 反转链表的后半部分从慢指针开始反转链表的后半部分。 比较前后两部分将反转后的后半部分与原始链表的前半部分进行比较如果每个节点都相等则是回文链表。
代码实现
public class Solution { public boolean isPalindrome(ListNode head) { // 如果链表为空或只有一个节点直接返回true if (head null || head.next null) { return true; } // 使用快慢指针找到链表的中点 ListNode slow head; ListNode fast head; ListNode prev null; while (fast ! null fast.next ! null) { prev slow; slow slow.next; fast fast.next.next; } // 如果链表长度为奇数则跳过中点 if (fast ! null) { slow slow.next; } // 反转链表的后半部分 ListNode secondHalfHead reverseList(slow); // 比较前半部分和反转后的后半部分 ListNode p1 head; ListNode p2 secondHalfHead; while (p2 ! null) { if (p1.val ! p2.val) { return false; } p1 p1.next; p2 p2.next; } return true; } // 反转链表的方法 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; }
}
方法二思路分析使用栈 遍历链表将遍历到的每个节点的值压入栈中。然后再次遍历链表同时从栈中弹出元素比较从链表中取出的元素和从栈中弹出的元素是否相等。如果所有元素都匹配则链表是回文的。
public class Solution { public boolean isPalindrome(ListNode head) { StackInteger stack new Stack(); ListNode curr head; // 遍历链表将值压入栈 while (curr ! null) { stack.push(curr.val); curr curr.next; } // 再次遍历链表同时从栈中弹出元素进行比较 curr head; while (curr ! null) { if (curr.val ! stack.pop()) { return false; } curr curr.next; } return true; }
}
方法三思路分析使用数组 遍历链表将遍历到的每个节点的值存储在一个数组中。然后使用双指针技术一个从头开始一个从尾开始来比较数组中的元素。这种方法的空间复杂度是O(n)其中n是链表的长度。
public class Solution { public boolean isPalindrome(ListNode head) { ListInteger vals new ArrayList(); ListNode curr head; // 遍历链表将值存储在数组中 while (curr ! null) { vals.add(curr.val); curr curr.next; } // 使用双指针比较数组中的元素 int i 0, j vals.size() - 1; while (i j) { if (!vals.get(i).equals(vals.get(j))) { return false; } i; j--; } return true; }
}
