本文共 1580 字,大约阅读时间需要 5 分钟。
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2输出: false
示例 2:
输入: 1->2->2->1输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?# Definition for singly-linked list.# class ListNode(object):# def __init__(self, x):# self.val = x# self.next = Noneclass Solution(object): def isPalindrome(self, head): """ :type head: ListNode :rtype: bool """ if head == None : return True lst = [] p = head while p: lst.append(p.val) p = p.next return lst == lst[::-1]
以下是Java版本:
这道题让我们判断一个链表是否为回文链表,LeetCode中关于回文串的题共有六道,除了这道,其他的五道为,,, 和 .链表比字符串难的地方就在于不能通过坐标来直接访问,而只能从头开始遍历到某个位置。那么根据回文串的特点,我们需要比较对应位置的值是否相等,那么我们首先需要找到链表的中点,这个可以用快慢指针来实现,使用方法可以参见之前的两篇 和 ,我们使用快慢指针找中点的原理是fast和slow两个指针,每次快指针走两步,慢指针走一步,等快指针走完时,慢指针的位置就是中点。我们还需要用栈,每次慢指针走一步,都把值存入栈中,等到达中点时,链表的前半段都存入栈中了,由于栈的后进先出的性质,就可以和后半段链表按照回文对应的顺序比较了。
思路二:
遍历链表,利用栈先进后出的性质,把链表前半段放入栈中,逐个弹出和链表后半段比较。(当然也可以全部放入栈)/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public boolean isPalindrome(ListNode head) { Stackstack = new Stack (); ListNode node = head; while(node != null) { stack.push(node.val); node = node.next; } while(!stack.empty()) { int value = stack.pop(); if(value != head.val) { return false; }else{ head = head.next; } } return true; } }
转载地址:http://mpuvi.baihongyu.com/