[LintCode] Palindrome Linked List

Tamic 發(fā)布于2019-08-14 15:12 / 2657人閱讀

摘要：

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

云服務(wù)器 GPU云服務(wù)器 linked palindrome LintCode LintCode134_LRU

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65446.html

相關(guān)文章

[Leetcode] Palindrome Linked List 回文鏈表

摘要：代碼尋找中點(diǎn)記錄第二段鏈表的第一個節(jié)點(diǎn)將第一段鏈表的尾巴置空將第二段鏈表的尾巴置空依次判斷 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? 反轉(zhuǎn)鏈表復(fù)...

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

摘要：請判斷一個鏈表是否為回文鏈表。然后是判斷是否是回文鏈表不考慮進(jìn)階要求的話，方法千千萬。好在這道題只要求返回布爾值，即便把原鏈表改變了也不用擔(dān)心。然后從原鏈表頭節(jié)點(diǎn)與反轉(zhuǎn)后后半部分鏈表頭節(jié)點(diǎn)開始對比值即可。 ?請判斷一個鏈表是否為回文鏈表。 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

摘要：請判斷一個鏈表是否為回文鏈表。然后是判斷是否是回文鏈表不考慮進(jìn)階要求的話，方法千千萬。好在這道題只要求返回布爾值，即便把原鏈表改變了也不用擔(dān)心。然后從原鏈表頭節(jié)點(diǎn)與反轉(zhuǎn)后后半部分鏈表頭節(jié)點(diǎn)開始對比值即可。 ?請判斷一個鏈表是否為回文鏈表。 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

摘要：建立結(jié)點(diǎn)，指向可能要對進(jìn)行操作。找到值為和的結(jié)點(diǎn)設(shè)為，的前結(jié)點(diǎn)若和其中之一為，則和其中之一也一定為，返回頭結(jié)點(diǎn)即可。正式建立，，以及對應(yīng)的結(jié)點(diǎn)，，然后先分析和是相鄰結(jié)點(diǎn)的兩種情況是的前結(jié)點(diǎn)，或是的前結(jié)點(diǎn)再分析非相鄰結(jié)點(diǎn)的一般情況。 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