[자바 알고리즘 인터뷰] 8장 연결 리스트(1) 팰린드롬 연결 리스트

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

 

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

 

 

풀이 1) 스택을 이용한 풀이 

 

- 팰린드롬 여부를 판별하기 위해서는 앞뒤로 모두 추출할 수 있는 자료구조가 필요 

- 연결 리스트를 먼저 스택에 복사해 넣은 다음 ,다시 연결 리스트를 앞에서부터 이동하면서 값을 조회하고, 스택은 pop()으로 추출하면서 뒤에서부터 값을 끄집어내어 함께 비교해본다. 

 

- 연결 리스트를 스택에 삽입

//연결리스트에 스택을 삽입
        ListNode node = head;
        while(node!=null)
        {
            stack.add(node.val);
            node = node.next;
        }

 

- 연결 리스트를 앞에서부터 이동하면서 값을 조회

- 스택은 pop()으로 하나씩 추출하면서 뒤에서부터 값을 끄집어 낸다. 

- 하나라도 다르다면 false를 리턴하고, 연결 리스트 끝까지 갈 동안 모두 일치한다면 true를 리턴 

 //연결 리스트가 모두 빌 때까지 비교 
 while(head!=null)
 {
    //연결 리스트와 스택에서 추출한 값을 비교해 팰린드롬 판별
    if(head.val != stack.pop())
    {
        return false;
     }
         head = head.next;
   }
   return true;

 

 

 

/**
 * 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;
    }
}

43 밀리초 

 

 

풀이 2) 데크를 이용한 풀이 

 

- 데크(Deque)는 이중 연결 리스트 구조로 양쪽 방향 모두 추출하는 데 시간 복잡도가 O(1)이 걸린다. 

 

class Solution {
    public boolean isPalindrome(ListNode head) {
        Deque<Integer> deque = new LinkedList<>();

        //연결 리스트를 데크에 삽입
        ListNode node = head;
        while(node!=null)
        {
            deque.add(node.val);
            node = node.next;
        }

        //데크가 모두 비거나(짝수 개일때) 1개 이하(홀수 개일때) 될 때까지 비교
        while(!deque.isEmpty() && deque.size()>1) {
            //데크의 양 끝을 추출해 팰린드롬 여부 확인
            if(deque.pollFirst()!=deque.pollLast()) {
                return false;
            }
        }
        return true;
    }
}

28 밀리초

 

 

풀이 3) 러너를 이용한 풀이 

 

러너(Runner) 기법

 

- 연결리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법

- 한 포인터가 다른 포인어보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다. 

- 빠른 러너(Fast Runner)는 두 칸씩 건너뛰고 느린 러너(Slow Runner)는 한 칸씩 이동하게 한다. 

- 이때 빠른 러너가 연결 리스트의 끝에 도달하면, 느린 러너는 정확히 연결 리스트의 중간 지점을 가리키게 된다. 

 

 

- 느린 러너가 중간까지 이동한 후에는 나머지 경로를 역순으로 하여 연결 리스트 rev를 만들어 나간다.

- rev를 만들고 난 후에는 원래 연결 리스트와 일치하는지 확인하면 된다. 

 

출처 : 자바 알고리즘 인터뷰 with 코틀린 저자 : 박상길 <책만>

 

 

- 입력값이 홀수일 때는 느린러너가 한 칸 더 앞으로 이동해 중앙의 값을 빗겨나가야 한다. 

- 왜냐하면 입력값 1->2->3->2->1에서 3은 중앙에 위치한 값으로, 팰린드롬 체크에서 배제되어야 하기 때문이다.

- 이는 fast가 아직 null이 아닌 경우로 간주할 수 있으며, 따라서 이 경우 slow를 한 칸 더 이동해 마무리한다. 

//홀수 개일 때 느린 러너가 한칸 더 앞으로 가도록 처리
if(fast!=null)
    slow = slow.next;

 

- 중간에 도달한 느린 러너를 기준으로 하여 역순으로 연결 리스트를 만들어 나간다. 

- rev는 느린 러너의 위치를 기준으로 하여 만든느 역순 연결 리스트이며, 여기서는 남아 있는 2->1의 역순인 1->2 형태로 최종적으로 값이 만들어 진다. 

/rev 연결 리스트를 끝까지 이동하며 비교 
while(rev!=null)
{
   //역순 연결 리스트 rev와 기존 연결 리스트 head를 차례대로 비교
   if(rev.val != head.val)
         return false;
   rev = rev.next;
   head = head.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;
        }

        //홀수 개일 때 느린 러너가 한칸 더 앞으로 가도록 처리
        if(fast!=null)
            slow = slow.next;
        
        //중간에 도달한 느린 러너를 기준으로 하여 역순 연결 리스트를 만든다. 
        ListNode rev = null;
        while(slow!=null)
        {
            //느린 러너로 역순 연결 리스트 rev를 만들어 나간다.
            ListNode next = slow.next;
            slow.next = rev;
            rev = slow;
            slow = next;
        }

        //rev 연결 리스트를 끝까지 이동하며 비교 
        while(rev!=null)
        {
            //역순 연결 리스트 rev와 기존 연결 리스트 head를 차례대로 비교
            if(rev.val != head.val)
                return false;
            rev = rev.next;
            head = head.next;
        }

        return true;
    }
}

4밀리초