链表回文判断(基于链表反转)—Java实现
程序员文章站
2022-07-05 09:48:19
学习数据结构的时候遇到一个经典的回文链表问题 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 如果有链表反转的基础,实现链表回文判断就简单的多,如果对反转链表不熟悉,可以参考这篇 "博客" 。 思路很简单,先找到链表的中间Node,采用的快慢指针 ......
学习数据结构的时候遇到一个经典的回文链表问题
- 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
如果有链表反转的基础,实现链表回文判断就简单的多,如果对反转链表不熟悉,可以参考这篇。
思路很简单,先找到链表的中间Node,采用的快慢指针法。
- 慢指针一次走一步,快指针一次走两步,当快指针触底的时候,慢指针到达了重点,如果链表总数是偶数,则慢指针停在相对左边的Node上。
- 找到中点后,对中点后面的链表进行反转。
- 从头尾开始向中间移步,每次比较是否相同。
import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class PalindromeList { //第一步找到中点 //从中点开始将后续结点反转 //两遍开始next比较直到相遇 public boolean chkPalindrome(ListNode A) { ListNode node1 = A; ListNode node2 = A; while(node2.next!=null&&node2.next.next!=null){ node1=node1.next; node2=node2.next.next; } ListNode head2 = node1.next; //反转链表过程,推荐采用遍历法 ListNode temp = null; ListNode pre = null; while(head2!=null){ temp = head2.next; head2.next = pre; pre = head2; head2=temp; } //对比过程 ListNode n1 = A; ListNode n2 = pre; //最后一个节点 while(n1.next!=null){ if(n1.val!=n2.val){ return false; } n1=n1.next; n2=n2.next; } return true; } }
上一篇: 全球大学排名前50名