[LeetCode] 234. Palindrome Linked List

Problem

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

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

Solution

Logic

1. Stack을 선언하고, 연결 리스트의 중간까지 포인터를 이동시키면서 노드들을 담는다.

2. 중간 이후부터 Stack의 노드를 꺼내서 비교한다.

3. 값이 다른 노드가 발견되면 false를 반환하고 그렇지 않으면 true를 반환한다.

   Code

   /**
    * Definition for singly-linked list.
    * public class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode() {}
    *     ListNode(int val) { this.val = val; }
    *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    * }
    */
   class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            stack.push(slow);
            if (fast.next == null) break;
            slow = slow.next;
            fast = fast.next.next;
        }
        while (slow != null) {
            if (stack.pop().val != slow.val) return false;
            slow = slow.next;
        } return true;
    }
   }
   

   Time Complexity

   • 연결 리스트의 길이를 n이라 가정할 떄, while반복문 2번 거치면서 n번의 계산이 수행된다. 따라서 본 솔루션은 O(n)의 시간 복잡도를 가진다.