연결리스트가 팰린드롬 구조인지 판별하라.
input : 1 -> 2 -> 3 -> 2 -> 1
output : true
ListNode 란 ? java에서 기본적으로 제공하는 형태가 아니고 leetCode에서 제공하는 형태이다.
문제를 보면
/**
* 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가 어떤 클래스인지 명시해준다.
int val 이라는것을 값으로 쓰고
next 라는것으로 다음 노드를 지칭한다.
해당 자료형이 java 에서 내가모르는 자료형이 있던가? 고민하지말자.
일단 ListNode는 List<String> 과 같은 ArrayList완 다르다.
index를 쓸수없고, ListNode 에 [1,2,3] 이 담겨있다고하면 얘네는 앞에서부터 순차적으로 가져올수있다.
또한 가져올때 head 라는 요소를 사용하여 순차적으로 가져올수있다. head는 해당 리스트의 시작을 나타내는 포인터 개념이다.
이것은 한번 사용하면 오염되어, 다음 문제때 head 즉 시작위치를 알 수없게 되기때문에 사용할때 유의해야한다.
해당 문제는 ListNode가 팰린드롬인가? 를 묻는 문제이기 때문에 해당 리스트를 뒤집은 결과가 해당리스트와 동일한지 체크하겠다.
리스트 추출방법 1 - Stack
Stack 을 활용하여 리스트를 추출해보자.
class Solution {
public boolean isPalindrome(ListNode head) {
Stack<Integer> stack = new Stack<>();
}
}
이런식으로 선언하면 안된다고 책에 써있긴 했지만 일단, ListNode 를 담을 스택을 선언해준다.
그리고 파라미터로 들어온 head, 즉 팰린드롬인지 알고싶은 데이터를 사용하면 head위치가 손상되어버리기때문에
별도 ListNode에 해당데이터를 넣어준다.
class Solution {
public boolean isPalindrome(ListNode head) {
Stack<Integer> stack = new Stack<>();
LisNode node = head;
}
}
이제 node 에 있는 값을 순서대로 stack 에 쌓아준다
ListNode 는 index를 쓸 수 없고 순차적인 접근밖에 지원되지 않으므로 while문을 써준다.
class Solution {
public boolean isPalindrome(ListNode head) {
Stack<Integer> stack = new Stack<>();
LisNode node = head;
while(node != null) {
stack.add(node.val);
node = node.next;
}
}
}
이렇게 담은 node와 head가 같은지 비교해준다
만약 head.val 과 stack.pop 이 한번이라도 같지않을 경우에는 무조건 팰린드롬이 아니기때문에 false를 보내주고
해당 if문에 걸리지않을 동안에는 계속 순차적으로 비교해야하기때문에 next를 처리해준다
class Solution {
public boolean isPalindrome(ListNode head) {
Stack<Integer> stack = new Stack<>();
LisNode node = head;
while(node != null) {
stack.add(node.val);
node = node.next;
}
while (head != null) {
if (head.val != stack.pop()) {
return false;
}
head = head.next;
}
return true;
}
}
stack 은 후입선출이기때문에 stack.pop() 처리를 하면 스택에서 해당값을 꺼내고 해당값은 없애준다.
그래서 얘도 별도로 index 를 지칭해주지않아도 된다.
if문에 걸리지않았다면 true 이므로 true 반환하고 끝.
리스트 추출방법 2 - Deque
Stack 보다 빠르게 처리될 수 있는 Deque를 사용해보자.
여기서의 Deque 구현은 LinkedList로 했는데, 다른 식으로 구현이 가능하다.
하지만 현재는 연결리스트를 공부하고있으므로 LinkedList로 구현했다.
class Solution {
public boolean isPalindrome(ListNode head) {
Deque<Integer> deque = new LinkedList<>();
}
}
그리고 Stack 과 동일하게, 별도 node를 만들어줘서 head를 저장할 필요가 없다.
우리는 Deque 의 앞뒤를 비교할것이기때문에 !
class Solution {
public boolean isPalindrome(ListNode head) {
Deque<Integer> deque = new LinkedList<>();
while(head != null) {
deque.add(head.val);
head = head.next;
}
}
}
deque 에서도 add를 써준다.
Deque 는 앞/뒤에서 모두 추출 가능하므로 Deque 의 맨앞 & 맨뒤를 비교하면 팰린드롬인지 알수있다.
그리고 만약 해당 리스트가 짝수면 list.size 는 0이 되겠지만, 홀수라면 list.size = 1 이 되어버리므로, 1 이하였을때 종료되도록 해주자
class Solution {
public boolean isPalindrome(ListNode head) {
Deque<Integer> deque = new LinkedList<>();
while(head != null) {
deque.add(head.val);
head = head.next;
}
while(!deque.isEmpty() && deque.size() > 1 ) {
if(deque.pollFirst() != deque.pollLast()) {
return false;
}
}
return true;
}
}
이렇게하면 deque가 empty 이면 (짝수) 종료되고, size가 1이어도 (홀수) 종료된다.
pollFirst() , pollLast() 는 각각 값을 꺼내오고 해당값을 탈출시키기때문에 deque 에서 값이 계속 빠져나간다.
Deque 문법
- 앞쪽에서 작업:
- addFirst(E e) - 맨 앞에 요소 추가
- removeFirst() - 맨 앞의 요소 제거
- peekFirst() - 맨 앞의 요소를 반환 (제거하지 않음)
- 뒤쪽에서 작업:
- addLast(E e) - 맨 뒤에 요소 추가
- removeLast() - 맨 뒤의 요소 제거
- peekLast() - 맨 뒤의 요소를 반환 (제거하지 않음)
- 일반 큐 작업:
- offer(E e) - 맨 뒤에 요소 추가 (큐의 add와 동일)
- poll() - 맨 앞의 요소 제거 및 반환
- peek() - 맨 앞의 요소를 반환 (제거하지 않음)
- 스택 작업:
- push(E e) - 맨 앞에 요소 추가 (스택의 push와 동일)
- pop() - 맨 앞의 요소 제거 및 반환 (스택의 pop과 동일)
기존의 stack 에서는 본체 node와 stack 을 비교했다면 deque 를 사용할 경우 해당 Deque 하나에서 앞뒤를 구분한다.
리스트 추출방법 - Runner
팰린드롬 연결 리스트 문제를 푸는 정공법은 러너기법이라고 한다.
ListNode 2개를 만들어서 한개는 .next.next 나머지한개는 .next 를 하게해서 빠른러너/느린러너를 생성한다.
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
}
}
두 ListNode 모두 head 를 담아놓고 초기화를 시켜준다.
그리고 fast 가 2칸 (.next.next)을 가고 slow가 1칸 (.next)을 가게 해준다.
그러면 결국에는 fast가 끝에다다랐을때 slow는 딱! 중간에 위치하게된다.
하지만 이것은 홀수의 이야기이고, 만약 짝수일때는 이미 .next 까지만 값이 있고 .next.next 에는 값이없다!
때문에 홀수/짝수를 모두 생각해서 조건을 넣어준다.
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
while(fast != null && fast.next != null {
fast = fast.next.next;
slow = slow.next;
}
}
}
fast == null 이면 홀수로 끝났고 fast != null 이지만 fast.next == null 일때는 짝수로 끝나기때문에 저렇게 조건을 해준다.
그런데 여기까지만처리해주면 여전히 slow는 1칸을 마저 가지못하고 남아있기때문에 한칸을 마저 옮겨준다.
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
while(fast != null && fast.next != null {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) {
slow = slow.next;
}
}
}
이렇게까지 되면 fast 는 head 를 모두 끝냈고, slow 는 head의 딱 정중앙에 있는것이다.
fast 는 slow를 구하기위해 희생된 느낌이다.
자 이제 배열의 정중앙에 있는 slow를 이용해서 팰린드롬 여부를 확인해보자.
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && first.next != null) {
fast = fast.next.next;
slow = slow.next
}
if (fast != null) {
slow = slow.next;
}
ListNode rev = null;
while (slow != null) {
ListNode next = slow.next;
slow.next = rev;
rev = slow;
slow = next;
}
}
}
여기서 뇌정지가 왔는데 하나하나 살펴보자.
첫번째 루프
ex) [1, 2, 3, 4, 3, 2, 1]
ListNode rev = null;
while (slow != null) {
ListNode next = slow.next; // next = 3
slow.next = rev; // slow.next = null
rev = slow; // rev = 4
slow = next; // slow = 3
}
현재 slow : 4 -> 3 -> 2 -> 1
next 에 slow.next 를 담아둔다
slow.next = rev;
이 행위로 slow.next 를 null로 만들어줬다.
지금 slow는 4 -> null 인것이다!!!
왜냐면 현재 slow는 냅두고 slow.next 를 덮어씌우기 해버렸으니까!
rev = slow;
이걸로 rev 에 현재 slow. 즉 4 -> null 를 담았다.
slow = next;
아까 저장해둔 slow.next 를 현재 slow 에 넣어준다.
그러면 4 -> null 이 아니라 다시 3 -> 2 -> 1 이 된다.
결국 rev : 4 -> null / slow : 3 -> 2 -> 1
두번째 루프
[1, 2, 3, 4, 3, 2, 1]
ListNode rev = null;
while (slow != null) {
ListNode next = slow.next; // next = 2
slow.next = rev; // slow.next = 4
rev = slow; // rev = 3
slow = next; // slow = 2
}
다시 next 에 2 -> 1 넣어두고 slow.next = 4 -> null 을 해뒀다.
이때 slow는 3 -> 4 -> null 이 된다 !!
그럼 그것을 rev 에 넣고 slow 에는 2 -> 1 을 (slow.next)를 넣어준다.
rev : 3 -> 4 -> null
slow : 2 -> 1
세번째 루프
[1, 2, 3, 4, 3, 2, 1]
ListNode rev = null;
while (slow != null) {
ListNode next = slow.next; // next = 1
slow.next = rev; // slow.next = 3
rev = slow; // rev = 2
slow = next; // slow = 1
}
slow.next = rev 를 해주면 현재 slow 는 2 -> 3 -> 4 -> null
rev : 2 -> 3 -> 4 -> null
slow : 1
네번째 루프
[1, 2, 3, 4, 3, 2, 1]
ListNode rev = null;
while (slow != null) {
ListNode next = slow.next; // next = null
slow.next = rev; // slow.next = 2
rev = slow; // rev = 1
slow = next; // slow = null
}
rev : 1 -> 2 -> 3 -> 4 -> null
slow : null
이렇게 루프를 돌아서 연결리스트의 반절 ~ 후반부를 rev에 저장했다.
뒤쪽에 쌓이는게아니라 앞에 쌓이는게 어색하지만.. 여튼 완료. 이제 이것과 원래 head를 비교해보자
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) {
slow = slow.next;
}
ListNode rev = null;
while (slow != null) {
ListNode next = slow.next;
slow.next = rev;
rev = slow;
slow = next;
}
while (rev != null) {
if (head.val != rev.val) {
return false;
}
rev = rev.next;
head = head.next;
}
return true;
}
}
어짜피 rev는 head의 반절만 있으니까 while 문 조건으로 rev가 null이면 빠져나오게했다
왜이렇게 어렵게해서 만든담?!! 속도때문이지만... ㅠㅠ
