5주차. 연결 리스트(팰린드롬 연결 리스트)

13. 팰린드롬 연결 리스트

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

Palindrome Linked List - LeetCode

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

- 예제1
  📝입력

head = [1,2,2,1]

  💻출력

true

  
 - 예제2

  📝입력

head = [1,2]

  💻출력

false

    
📌풀이(Deque 활용)
11ms, 58mb

public boolean isPalindrome(ListNode head) {
    Deque<Integer> deque = new LinkedList<>();
    ListNode tempNode = head;
    while(tempNode != null){
        deque.add(tempNode.val);
        tempNode = tempNode.next;
    }
    while(deque.size()>1){
        if(deque.pollFirst() != deque.pollLast()) return false;
    }
    return true;
}

- 1주차에서 배웠던 방법인 Deque를 활용했다.

- 연결리스트에 담긴 데이터를 Deque에 넣어주고 Deque의 앞 데이터와 뒤 데이터를 빼가면서 비교해준다.

 

📌풀이(Runner 기법 활용)
3ms, 59.1mb

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head, rev = null;
		// 런너기법활용
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
		// 역순 뒤집기
        while(slow != null) {
            ListNode next = slow.next;
            slow.next = rev;
            rev = slow;
            slow = next;
        }

        fast = head;
        slow = rev;
		// 비교
        while (slow != null) {
            if (fast.val != slow.val) return false;
            fast = fast.next;
            slow = slow.next;
        }

        return true;
    }
}

- 책에서 소개한 Runner 기법을 활용했다. 

- Runner 기법에 대해 찾아보니, 책에서 임의로 붙인 워딩인 것 같았다. 플로이드 순환 찾기 알고리즘의 일부를 활용한 것으로 보인다.

- slow는 한칸 씩 fast는 두칸 씩 이동한다. 그러므로 fast가 끝으로 다다르면 slow는 연결리스트의 중간 위치에 위치할 수 밖에 없다.

- 이때 slow를 역순으로 뒤집어준다. 중간에서 끝 부분에 다다르는 데이터들이 역순으로 재조립된다.

- 역순으로 바꿔준 연결리스트를 담은 rev와 fast를 비교한다. deque 방식을 알면 왜 이렇게 비교하는지 이해가 쉬울 것이다.