`

LeetCode 234 - Palindrome Linked List

 
阅读更多

Given a singly linked list of characters, write a function that returns true if the given list is palindrome, else false.

METHOD 1 (Use a Stack)
A simple solution is to use a stack of list nodes. This mainly involves three steps.
1) Traverse the given list from head to tail and push every visited node to stack.
2) Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node.
3) If all nodes matched, then return true, else false.

Time complexity of above method is O(n), but it requires O(n) extra space. Following methods solve this with constant extra space.

public boolean isListPalindrome(ListNode head) {
	Stack<ListNode> stack = new Stack<>();
	ListNode node = head;
	while(node != null) {
		stack.push(node);
		node = node.next;
	}
	while(head != null) {
		if(head.val != stack.pop().val) return false;
		head = head.next;
	}
	return true;
}

 

METHOD 2 (By reversing the list)
This method takes O(n) time and O(1) extra space.
1) Get the middle of the linked list.
2) Reverse the second half of the linked list.
3) Check if the first half and second half are identical.
4) Construct the original linked list by reversing the second half again and attaching it back to the first half

public boolean isListPalindrome(ListNode head) {
	if(head==null || head.next==null) return true;
	ListNode walker = head, runner = head;
	while(walker!=null && runner!=null) {
		walker = walker.next;
		runner = runner.next;
		if(runner!=null) {
			runner = runner.next;
		}
	}
	ListNode h = reverseLinkedList(walker);
	while(h!=null && head!=null) {
		if(h.val != head.val) return false;
		h = h.next;
		head = head.next;
	}
	return true;
}

public ListNode reverseLinkedList(ListNode head) {
	ListNode dummy = new ListNode(0);
	ListNode pre = dummy;
	while(head != null) {
		ListNode next = head.next;
		head.next = pre.next;
		pre.next = head;
		head = next;
	}
	return dummy.next;
}

重构了下代码:

public boolean isPalindrome(ListNode head) {
    if(head == null || head.next == null) return true;
    ListNode slow = head, fast = head.next;
    while(fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next;
        if(fast != null) fast = fast.next;
    }
    ListNode h = slow.next;
    slow.next = null;
    while(h != null) {
        ListNode next = h.next;
        h.next = slow.next;
        slow.next = h;
        h = next;
    }
    ListNode l1 = head, l2 = slow.next;
    while(l2 != null) {
        if(l1.val != l2.val) return false;
        l1 = l1.next;
        l2 = l2.next;
    }
    return true;
}

 

另外,还可以用递归的方法。

递归方法参见:

http://www.geeksforgeeks.org/function-to-check-if-a-singly-linked-list-is-palindrome/

分享到:
评论

相关推荐

    python-leetcode题解之234-Palindrome-Linked-List.py

    python python_leetcode题解之234_Palindrome_Linked_List.py

    Leetcode 234. Palindrome Linked List

    方法1  思路:将链表中的元素都保存list中,并判断这个list和反转后的list,是否相同,如果相同,则回文;否则,则不回文。...# Definition for singly-linked list. # class ListNode(object): # def __i

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的leetcode在线编程题解

    linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to...

    leetcode卡-leetcode:利特码解决方案

    Palindrome linked list Linked List Cycle trees Convert Sorted Array to Binary Search Tree string and search First Bad Version Dynamic Programing *** Climbing Stairs Set Matrix Zeroes API System....

    leetcode跳跃-leetcode:leetcode题解

    例如,“回文链表”(Palindrome Linked List)要求判断一个链表是否为回文结构,这就需要对链表的遍历和反转有深刻理解。 困难难度的题目通常需要开发者具备扎实的算法基础和创新思维。这些题目往往没有明显的解决...

    leetcode2sumc-LeetCode:LeetCode的一些题目

    leetcode 2 sum c LeetCode 帮助文档 帮助文档存放在Help文件夹下。 文件名 文件描述 ...complexitypython.txt Python的一些常规操作的复杂度统计 ...Linked List(链表) ...List ...Linked ...Palindrome Linked List

    leetcode338-Leetcode:一些过滤leetcode问题的解决方案

    234.Palindrome 链表: | 725. 分部分拆分链表: | 328.奇偶链表:| 哈希表: 问题及解决方法: 1.二和:| 594.最长和谐子序列:| 128.最长连续序列:| 数组和矩阵 问题及解决方法: 283.移零:| 566.重塑矩阵: | ...

    leetcode中325题python-leetcode:leetcode

    reverse-linked-list-ii(Reverse a Sub-list) 141 环形链表 linked-list-cycle 142 环形链表 II linked-list-cycle-ii 143 重排链表 reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双...

    LeetCode最全代码

    * [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...

    LeetCode3 Longest Substring Without Repeating Characters

    Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...

    算法-leetcode-剑指offer上的题很多

    - **链表(Linked List)**: 由一系列节点组成的集合,每个节点包含数据部分和指向下一个节点的指针。 - **二叉树(Binary Tree)**: 一种树形数据结构,每个节点最多有两个子节点,通常用于实现快速查找和排序操作。 - ...

    Leetcode题目+解析+思路+答案.pdf

    - **Flatten Binary Tree to Linked List**:将二叉树展平为单链表。 - **Validate Binary Search Tree**:验证一个二叉树是否为二叉搜索树。 - **Recover Binary Search Tree**:恢复二叉搜索树中的两个错误节点...

    javalruleetcode-leetcode:力码解决方案

    [回文链表](md/Palindrome Linked List.md) - 2015-10-06 [数字一](md/数字一.md) - 2015-10-06 [使用栈实现队列](md/使用栈实现队列.md) - 2015-10-06 [BST 中的第 K 个最小元素](md/BST.md 中的第 K 个最小元素) -...

    Leetcode部分试题解析

    19. **Palindrome Linked List** 和 **Palindrome Number**:判断链表或数字是否为回文。链表可以用双指针,数字可以转化为字符串后再判断。 20. **Plus One**:给数组中的所有数字加一。理解进位的概念,从数组...

    uber leetcode

    #### 八、Reverse Linked List - **知识点:**链表操作、迭代。 - **题目描述:**反转一个单链表。 - **应用场景:**链表的基本操作之一,常用于链表的排序、合并等高级操作。 #### 九、Palindrome Permutation - *...

    javalruleetcode-JavaInterviewChecklist:要检查的Java事项

    leetcode 面试清单 Java 比较器与比较器 哈希 静止的 例外 线 泛型 算法 链表 Linked List Cycle Remove Nth Node From End of List Merge Two Sorted Lists 两个链表的交集 Remove Duplicates from Sorted List ...

    LeetCode练习答案

    - **反转链表(Reverse Linked List)**: 反转一个单链表。 - **两两交换链表节点(Swap Nodes in Pairs)**: 给定一个链表,交换它相邻节点成对出现的形式。 - **排序链表(Sort List)**: 对一个链表进行排序。 - **旋转...

    leetcodepython001-Algorithm:关于数据结构和算法的问题(Leetcode、编程之美和课程作业)

    Palindrome Number C++ 2016/4/26 Easy 044 Wildcard Matching Python 2016/4/1 Hard 051 N-Queens C++ 2016/5/18 Hard 092 Reverse Linked List II Python 2017/11/28 Medium 095 Unique Binary Search Trees ...

    leetcode

    例如,"Reverse Linked List"要求反转链表,此时你需要熟练掌握链表的插入、删除和遍历操作。"Valid Palindrome"则需要利用栈或双指针来判断字符串是否为回文。 三、算法分析 LeetCode涵盖了许多经典算法,如排序...

Global site tag (gtag.js) - Google Analytics