[LeetCode] - Palindrome Linked List

Linked List가 주어지고 해당 리스트가 회문으로 구성되어 있으면 true 아니면 false

생각해보자

Palindrome이란 회문이다.
회문이란 패턴이 반복되는것을 의미한다.
LinkedList에서 회문을 검증하기 위해서는
head가 null이 될 때 까지 순회하며
패턴이 반복되는지를 체크해야한다.
head가 null이라면 true를 리턴
그렇지 않다면 
패턴이 반복된다는 것을 컴퓨터 시점에서 생각해보자.
ex) 1
1 2 2 1
head가 null이 아님
1 next 2 next 2 next 1 next null out
1 next 2 next null
회문이라면 중간에 같은 수가 반복되는 부분이 필요
그렇다면 temp같은 변수를 둬서 
직전에 수와 같은 부분이 없다면 return false
홀수라면 return false 1 2 1 -> false
1 2 2(체크포인트) 1
1 2 3 3(체크포인트) 2 1

-> 그냥 모조리 stack에 넣고
pop하면서 head와 비교하며 진행

1차 시도

/**
 * 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; }
 * }
 */
import java.util.*;
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null) return true;
        ListNode node = head; // 헤드의 첫번째 부분을 체크하기 위한 node
    
        Stack<Integer> stack = new Stack<Integer>(); 
        
        while(head != null) {	// Time complexity O(N), space complexity O(N)
            stack.push(head.val);
            head = head.next;
        }
        
        while(!stack.isEmpty()) { // Time complexity O(N), space complexity O(N)
            if(node.val != stack.pop()) return false;
            node = node.next;
        }
        // Time complexity O(2N), space complexity O(2N) -> O(N) O(N)
        // 가장 큰 범위가 10만이므로 stack에 10만개 넣고
        // stack이 빌 때까지 pop하지만 if문에서 걸릴것이므로 회문일 경우 최악-> 5만
        // 15만 연산 + stack에 10만개의 값 저장
        return true;
    }
}

Runtime: 10 ms
Memory Usage: 51.2 MB
/*
수의 범위가 0~9라서 byte로 치환해서 해봤는데 공간복잡도에 차이가 없었다.
10 ms	51.2 MB
import java.util.*;
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null) return true;
        ListNode node = head; // 헤드의 첫번째 부분을 체크하기 위한 node
    
        Stack<Byte> stack = new Stack<>();
        
        while(head != null) {
            stack.push((byte)head.val);
            head = head.next;
        }
        
        while(!stack.isEmpty()) {
            if((byte)node.val != stack.pop()) return false;
            node = node.next;
        }
        return true;
    }
}
*/

3ms solution (이해 안되니 이게 어떻게 동작하는지 물어볼 것)

/**
 * 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) {
     ListNode fst=head;
        ListNode slow=head;
        ListNode prev=null;
        ListNode temp=null;
        while(fst!=null && fst.next!=null)
        {
            fst=fst.next.next;
            temp=slow.next;
            slow.next=prev;
            prev=slow;
            slow=temp;
        }
        if(fst!=null)
            slow=slow.next;
        ListNode head1=prev;
        ListNode head2=slow;
        while(head1!=null && head2!=null)
        {
          if(head1.val!=head2.val)
          return false;
            head1=head1.next;
            head2=head2.next;
        }
        if(head1==null && head2==null)
            return true;
        else
            return false;
    }
}
Runtime: 3 ms
Memory Usage: 49 MB