Leetcode日记–234. Palindrome Linked List

发布于 2020-10-23  112 次阅读


碎碎念:我决定了,半年内一定要做一个体检。冲,养生人!

题目如下:

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true


Follow up:
Could you do it in O(n) time and O(1) space?

思路:

方法一:随机存取

直接存到数组里,可以随机存取后,再用两端的双指针来从一头一尾遍历。比较是否值相同。

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<Integer>();

        // 将链表的值复制到数组中
        ListNode currentNode = head;
        while (currentNode != null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // 使用双指针判断是否回文
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

显然,这个方法的时间复杂度为O(n),空间复杂度也为O(n)。

方法二:栈

很容易观察到,若为回文序列,则前半段遍历结果和后半段遍历结果正好相反(若节点个数为奇数个,则后半段不包括中点)。

可以先遍历,并把值压入栈内,直到中点。然后再继续遍历后半段,并让前半段的值出栈,进行比较。

寻找中点我们可以使用快慢指针的方法(之前的某道题好像也使用了快慢针找中点的操作,可以顺便复习一下)。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        
        if (head.next == null) {
            return true;
        }

        // 思路一:使用栈
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }
        while (head != null) {
            if (head.val != stack.pop()) {
                return false;
            }
            head = head.next;
        }
        return stack.isEmpty();
    }
}

作者:dubyKim
链接:https://leetcode-cn.com/problems/palindrome-linked-list/solution/zhan-kuai-man-zhi-zhen-by-dubykim/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

这个方法的时间复杂度为O(n),空间复杂度为O(n)

方法三:反转链表

我们之前的方法,空间复杂度为O(n)的原因是因为我们需要一个结构来记录之前的结果进行对比,或者是直接变为可以随机存取的数据结构。

那我们有什么办法可以直接使用链表并不需要保存前面的结构呢?

我们想想前面使用栈的方法,我们是在比较前后部分,且他们是逆序的。那么,我们找到中点后,可不可以直接把后半部分逆序了呢?

参考这个206题,我们找到中点后,逆序后半段,然后就可以直接遍历前后两个半段进行比较。

代码如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null)
            return true;
        ListNode midNode = findMidleNode(head);
        ListNode newMidNode = reverseList(midNode.next);
        while(newMidNode!=null){
            if(newMidNode.val!=head.val)
                return false;
            newMidNode = newMidNode.next;
            head = head.next;
        }
        return true;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public ListNode findMidleNode(ListNode head){
        ListNode fast =  head;
        ListNode slow = head;
        while(fast.next!=null&&fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

}

你好哇!欢迎来到雷公马碎碎念的地方:)