要点理解 : 回文串是中心对称的
/** * @Description 链表类需要自定义 * @Date 2019/8/11 17:40 **/ class ListNode { int val; ListNode next; public ListNode(int x){ val=x; } } /** * @Description * @Date 2019/8/11 17:40 **/ public class PalindromeLinkedList { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } ListNode prev = null; ListNode slow = head; ListNode fast = head; // 直到快指针到达最后一个节点(链表长度为奇数时)或者刚刚跳出最后一个节点为止(链表长度为偶数时) while (fast != null && fast.next != null) { fast = fast.next.next; ListNode next = slow.next; slow.next = prev; prev = slow; slow = next; } // 如果链表的长度是奇数,则这个if块会让慢指针跳过正中间的那个节点 if (fast != null) { slow = slow.next; } while (slow != null) { if (slow.val != prev.val) { return false; } slow = slow.next; prev = prev.next; } return true; } @Test public void test() { // ListNode listNode = new ListNode("abccba"); // String // ListNode listNode = new ListNode(); ListNode head = new ListNode(1);//创建头节点 head.next = new ListNode(2);//再定义头节点的next域 head.next.next = new ListNode(3);//再定义头节点的next域 ListNode t = head.next.next; for(int i=4;i<=6;i++) {//创建一个简单的链表{1,2,3,4,5,...,9} t.next = new ListNode(7-i); t = t.next; } printListNode(head); System.out.println(); System.out.println(isPalindrome(head)); } }
代码参考: https://github.com/andavid/leetcode-java/blob/master/note/234/README.md 理解参考: 极客时间相关课程 https://time.geekbang.org/column/article/41013 的评论区 测试代码参考: https://blog.csdn.net/zsh_edison/article/details/89054814