[java] LeetCode 234. Palindrome Linked List

문제

https://leetcode.com/problems/palindrome-linked-list/description/

Palindrome Linked List - LeetCode

 

풀이

 

런너기법을 사용해서 구해보려고 코드를 봤는데... 시간이 많이 걸릴거 같아서..패쓰

우선 덱이나 스택을 학습하려고 푼 문제니 덱,스택을 사용해보자!!

 

덱

우선 간단하다 덱에 원소를 넣고, 앞과 뒤를 꺼내서 비교만 하면 된다

(ide 테스트용 코드)

package main;
import java.util.*;

 class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

public class Main {

		//1 23 2 1 
	   public static boolean isPalindrome(ListNode head) {
		   boolean answer = false;
		   
		   Deque<Integer> deque = new ArrayDeque<>();
		   while(head!=null) {
			   deque.addLast(head.val);
			   head=head.next;
		   }
		   
		   while(!deque.isEmpty()) {
			   int first = deque.pollFirst();
			   if(deque.size()==0) break;
			   int last = deque.pollLast();
			   if(first!=last) return false;
		   }
		   
		   return true;
	        
	    }

	public static void main(String[] args) {
	
		ListNode a = new ListNode();
		a.val=1;
		ListNode b = new ListNode();
		b.val=2;
		ListNode c = new ListNode();
		c.val=2;
		ListNode d = new ListNode();
		d.val=1;
		a.next=b;
		a.next.next=c;
		a.next.next.next=d;
		System.out.println(isPalindrome(a));
	
	}


}

 

 

스택

우선 ListNode의 크기를 구한다. 그리고 원래 ListNode head의 값과 stack에서 pop한 값이 일치하는지 비교한다!

package main;
import java.util.*;

 class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

public class Main {

	   public static boolean isPalindrome(ListNode head) {
		   boolean answer = false;
		   
	        Stack<Integer> st = new Stack<>();
	        ListNode nh = head;

	         int count=0;
	         while(head!=null){
	             st.add(head.val);
	             head=head.next;
	             count++;
	         }
	        
	         for(int i=0; i<count/2; i++){
	             if(st.pop()!=nh.val) return false;
	             nh= nh.next;
	         }
		   
		   return true;
	        
	    }
	   
	public static void main(String[] args) {
	
		ListNode a = new ListNode();
		a.val=1;
		ListNode b = new ListNode();
		b.val=2;
		ListNode c = new ListNode();
		c.val=2;
		ListNode d = new ListNode();
		d.val=1;
		a.next=b;
		a.next.next=c;
		a.next.next.next=d;
		System.out.println(isPalindrome(a));
	
	}


}

 

 

 

참조 블로그

https://velog.io/@jayb/LeetCode-234.Palindrome-Linked-List%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8

https://m.blog.naver.com/adamdoha/222174083093