JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

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

Code

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        ListNode mid = getMid(head);
        ListNode midNext = reverse(mid.next);

        while(midNext != null){
            if(head.val == midNext.val){
                head = head.next;
                midNext = midNext.next;
            } else {
                return false;
            }
        }

        return true;
    }

    private ListNode getMid(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;

        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }

        return prev;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def getMid(self, head: ListNode) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head

        slow = dummy
        fast = dummy

        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        return slow

    def reverse(self, head: ListNode) -> ListNode:
        prev = None
        while head:
            temp = head.next
            head.next = prev
            prev = head
            head = temp

        return prev


    def isPalindrome(self, head: ListNode) -> bool:
        if not head:
            return True

        mid = self.getMid(head)
        reversed = self.reverse(mid.next)

        while reversed and head:
            if reversed.val != head.val:
                return False

            reversed = reversed.next
            head = head.next

        return True