[LintCode] Palindrome Linked List

Tamic 发布于2019-08-14 15:12 / 2521人阅读

摘要：

Problem

Implement a function to check if a linked list is a palindrome.

Example

Given 1->2->1, return true.

Key

create new list nodes:

ListNode pre = null;
//null, 1-2-3-4
//1-null, 2-3-4
//2-1-null, 3-4
//3-2-1-null, 4
//4-3-2-1-null, null
while (head != null) {
    ListNode cur = new ListNode(head.val);
    cur.next = pre;
    pre = cur;
    head = head.next;
}

Solution

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode reversed = reverse(head);
        while (head != null) {
            if (head.val != reversed.val) return false;
            head = head.next;
            reversed = reversed.next;
        }
        return true;
    }
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        //null, 1-2-3-4
        //1-null, 2-3-4
        //2-1-null, 3-4
        //3-2-1-null, 4
        //4-3-2-1-null, null
        while (head != null) {
            ListNode cur = new ListNode(head.val);
            cur.next = pre;
            pre = cur;
            head = head.next;
        }
        return pre;
    }
}

私有云云服务器 linked palindrome LintCode LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65446.html

[Leetcode] Palindrome Linked List 回文链表

摘要：代码寻找中点记录第二段链表的第一个节点将第一段链表的尾巴置空将第二段链表的尾巴置空依次判断 Palindrome Linked List Given a singly linked list, determine if it is a palindrome. Follow up: Could you do it in O(n) time and O(1) space? 反转链表复...

glumes 2019-08-14 12:28 评论0 收藏0
[LintCode] Palindrome Partitioning

Problem Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example Given s = aab, return: [ [aa,b], [a,a,b...

NicolasHe 2019-08-14 15:11 评论0 收藏0
LeetCode 234：回文链表 Palindrome Linked List

摘要：请判断一个链表是否为回文链表。然后是判断是否是回文链表不考虑进阶要求的话，方法千千万。好在这道题只要求返回布尔值，即便把原链表改变了也不用担心。然后从原链表头节点与反转后后半部分链表头节点开始对比值即可。请判断一个链表是否为回文链表。 Given a singly linked list, determine if it is a palindrome. 示例 1: 输入: 1->...

luqiuwen 2019-08-16 18:41 评论0 收藏0
LeetCode 234：回文链表 Palindrome Linked List

摘要：请判断一个链表是否为回文链表。然后是判断是否是回文链表不考虑进阶要求的话，方法千千万。好在这道题只要求返回布尔值，即便把原链表改变了也不用担心。然后从原链表头节点与反转后后半部分链表头节点开始对比值即可。请判断一个链表是否为回文链表。 Given a singly linked list, determine if it is a palindrome. 示例 1: 输入: 1->...

hlcc 2019-07-31 11:30 评论0 收藏0
[LintCode] Swap Two Nodes in Linked List

摘要：建立结点，指向可能要对进行操作。找到值为和的结点设为，的前结点若和其中之一为，则和其中之一也一定为，返回头结点即可。正式建立，，以及对应的结点，，然后先分析和是相邻结点的两种情况是的前结点，或是的前结点再分析非相邻结点的一般情况。 Problem Given a linked list and two values v1 and v2. Swap the two nodes in th...

wua_wua2012 2019-08-14 14:41 评论0 收藏0