LeetCode 234 Palindrome Linked List

 

要点理解 : 回文串是中心对称的

 

/**
 * @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

 

上一篇:Leetcode-5150 Longest Chunked Palindrome Decomposition(段式回文)


下一篇:大数据和AI技术赋能 阿里云AIoT联合导学教育发布“导学号”智能作业灯