资讯专栏INFORMATION COLUMN

[LintCode] Palindrome Linked List

Tamic / 2591人阅读

摘要:

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;
    }
}

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

转载请注明本文地址: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 评论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 评论0 收藏0
  • LeetCode 234:回文链表 Palindrome Linked List

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

    luqiuwen 评论0 收藏0
  • LeetCode 234:回文链表 Palindrome Linked List

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

    hlcc 评论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 评论0 收藏0

发表评论

0条评论

Tamic

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<