[LintCode] Palindrome Linked List

Tamic 發布于2019-08-14 15:12 / 2635人閱讀

摘要：

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

GPU云服務器云服務器 linked palindrome LintCode LintCode134_LRU

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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