[linked list] palindrome linked list

✅ Problem

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

 

✅ Approach & Solution

공통

• 리스트의 앞과 뒤의 값을 비교하여 값이 다른 경우 팰린드롬이 아님

 

방식1) 추가 자료구조 사용

1-1) Stack 사용

/**
 * 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) {
        Stack<Integer> stack = new Stack<>();

        ListNode 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;
    }
}

 

1-2) Deque 사용

/**
 * 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) {
        Deque<Integer> deque = new LinkedList<>();
        // 연결리스트를 deque에 삽입
        ListNode node = head;
        while (node != null) {
            deque.add(node.val);
            node = node.next;
        }

        // deque이 모두 비거나 1개가 남을 때(데이터 개수 홀수일 때)까지 비교
        while (!deque.isEmpty() && deque.size() > 1) {
            if (deque.pollFirst() != deque.pollLast()) {
                return false;
            }
        }

        return true;
    }
}

 

 

방식2) 기존 자료구조 사용

• 러너 기법 활용
  • 빠른 러너(2칸 씩 이동), 느린 러너(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; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // 리스트의 중간 이후 지점부터 역순 연결 리스트를 생성한다.
        // 기존 연결 리스트와 비교한다. (다른 값이 있을 경우 palindrome이 아님)

        ListNode fast = head, slow = head;

        while (fast != null && fast.next != null) { // fast가 리스트의 끝에 도달했을 때
            fast = fast.next.next; // 2칸 씩 이동
            slow = slow.next; // 1칸 씩 이동
        }

        // 중간 값을 넘어가야 하기 때문에 홀수 개인 경우 slow를 한칸 더 이동
        if (fast != null) {
            slow = slow.next;
        }

        // slow 값 기준으로 역순 연결 리스트 생성
        ListNode rev = null; // 역순 연결 리스트의 시작 노드
        while (slow != null) {
            ListNode next = slow.next;
            slow.next = rev;
            rev = slow;
            slow = next;
        }
        
        // 기존 리스트와 역순 리스트 원소 비교
        // 한 개라도 다르면 palindrome이 아니므로 false 반환
        while (rev != null) {
            if (head.val != rev.val) {
                return false;
            }

            head = head.next;
            rev = rev.next;
        }

        return true;
    }
}

 

추가) 러너 기법

• 러너는 연결 리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법
  • 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있음
• 2개의 포인터는 빠른 러너와 느린 러너로 명칭하고, 빠른 러너는 2 칸씩 느린 러너는 1 칸씩 이동함
• 이때 빠른 러너가 연결 리스트의 끝에 도달하면, 느린 러너는 정확히 연결 리스트의 중간 지점을 가리키게 됨
  • 중간 위치를 찾아내면 전체 길이를 알아낼 수 있고, 여기서부터 값을 비교하거나 뒤집기를 시도하는 등의 활용 가능