leetcode 234. Palindrome Linked List

 

연결리스트가 팰린드롬 구조인지 판별하라.

 

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이면 빠져나오게했다

왜이렇게 어렵게해서 만든담?!! 속도때문이지만... ㅠㅠ