.leetcode(234. Palindrome Linked List)

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

 

3. 2022/05/02 시도

소요시간: 24분

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        // find mid
        ListNode slow = head;
        ListNode fast = head;
        while ( fast != null && fast.next != null) {
            slow = slow.next;    
            fast = fast.next.next;    
        }

        //reverse
        ListNode newHead = slow;
        ListNode current = slow.next;
        while (current != null) {
            ListNode temp = current.next;
            current.next = newHead;
            newHead = current;
            current = temp;
        }
        
        //compare
        ListNode reversed = newHead;
        while ( head != slow) {
            if (head.val != reversed.val) {
                return false;
            }
            
            head = head.next;
            reversed = reversed.next;
        }
        
        return true;
    }
}

풀이 접근 과정

먼저 edge케이스를 처리한다.

가운데 부분을 찾는다. 노드가 홀수인 경우, 예를들어 1,2,1일때, 2가 찾아지고 짝수인 경우, 예를들어 1,2,2,1일 때, 두번째 2가 찾아진다.그 값이 slow에 저장되므로 slow를 기준으로 한다.

slow를 기준으로 reverse를 만든다.
ex) [1,2,1] => 2가 찾아지고 [2,1]을 역으로 만들어준다.=> [1,2]
ex) [1,2,2,1] => 두번재 2가 찾아지고 [2,1]을 역으로 만들어준다.  => [1,2]

역으로 만들어진 링크드리스트를 기준으로 찾아진 slow노드까지 비교한다.
그러면 짝수든 홀수든 다 비교해볼 수 있다.

 

느낀점

• 약간의 변명을 하자면 졸려서 reverse하는 부분에서 조금 시간이 걸렸다.
• 가운데 점을 찾거나 비교하는건 어렵지 않은 부분이다.
• 3번째 풀어보는건데 시간은 가장 오래걸렸어도 공간복잡도 O(1)과 시간복잡도 O(n)을 만족하면서도 코드가 깔끔해서 마음에 든다.

---

 

2. 2022.01.05 시도

소요시간: 7분(2분 구상, 5분 코딩, arraylist), 15분(2분 구상, 13분 코딩, linkedlist)

# arraylist
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        List<Integer> nodes = new ArrayList<>();
        while(head != null) {
            nodes.add(head.val);
            head = head.next;
        }
        
        int half = nodes.size()/2;
        for(int x=0; x<=half; x++) {
            if (nodes.get(x) != nodes.get(nodes.size()-x-1)) {
                return false;
            }
        }
        
        return true;
    }
}

# linkedList
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        // get total length
        ListNode toKnowTheLength = head;
        int length=0;
        while(toKnowTheLength != null) {
            length++;
            toKnowTheLength=toKnowTheLength.next;
        }
        if (length == 1) {
            return true;
        }
        
        // get first and second half listnode
        int half = length/2;
        int counter=0;
        ListNode secondHalfListNode = head;
        while(counter<half +  ((length %2) == 1 ? 1 : 0)) {
            secondHalfListNode = secondHalfListNode.next;
            counter++;
        }
        ListNode firstHalfListNode = reverse(head, half);
        
        // compare
        while (firstHalfListNode != null) {
            if (firstHalfListNode.val != secondHalfListNode.val) {
                return false;
            }
            firstHalfListNode = firstHalfListNode.next;
            secondHalfListNode = secondHalfListNode.next;
        }
        
        return true;
    }
    
    private ListNode reverse(ListNode head, int until) {
        if (until == 0) {
            return head;
        }

        ListNode previous = null;
        while(until > 0) {
            ListNode temp = head.next;
            head.next = previous;
            previous = head;
            head = temp;
            until --;
        }
        
        return previous;
    }
}

풀이 접근 과정

palindrome을 알기위해서는 중간을 알아야하고 중간을 알기 위해서는 전체 길이를 알아야한다. 문제를 풀기 위해서는 길이값을 어떻게 아느냐, 어떻게 접근하느냐가 중요하다고 생각했다.

arraylist를 쓰면 두번만 읽어서 끝낼 수 있겠다. 즉 O(n)이 나오겠다 싶었다. 어차피 길이를 알기위해서는 전체를 한번 읽어야하므로 O(n)보다 빠른 시간복잡도는 불가능하다. 따라서 이건 해법이다. 다만 공간을 O(n)만큼 써야한다.

그래서 빠르게 arraylist로 풀이를 풀어보고는 공간을 안쓸 수 있는 방법을 생각해보았다. 길이를 알아낸다면 처음부터 중간까지는 reverse시켜버리면 되었다. 마침  reversed linked list를 학습한 터라 이를 이용해서 풀어보았다. 길이를 재고 링크 순서를 바꾸고 2개로 나뉜 리스트를 차례대로 비교해보며 결과를 확인한다. 공간복잡도 O(1)이 가능한 순간이었다.

 

느낀점

• 이미 풀어본 reversed linked list를 이용해 풀었을 때는 정말 짜릿했다. 공부가 2배로 되는 신나는 경험이다. 코드는 다소 지저분하지만 원하는 공간복잡도도 얻어내고 실제로 프로그램도 오류없이 돌아가니 뿌듯했다.
• 지난 시도를 살펴보니 기가막히게 그때도 reversed linked list방식을 사용해서 풀었다.
• 중간을 구할때 길이를 구해서 접근하는 방식이 아닌 fast, slow방식이 훨씬 깔끔하다.

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        
        ListNode secondEndNode = findSecondEndNode(head);
        ListNode secondHeadNode = reverseNode(secondEndNode);
        
        ListNode first = head;
        ListNode second = secondHeadNode;
        int index =0;
        while(second != null) {
            index++;
            if (first.val != second.val) {
                return false;
            }
            first = first.next;
            second = second.next;
        }
        
        return true;
    }
    
    private ListNode findSecondEndNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        
        return slow;
    }
    
    private ListNode reverseNode(ListNode head) {
        ListNode current = head;
        ListNode previous = null;
        while(current != null) {
            ListNode temp = current.next;
            current.next = previous;
            previous = current;
            current = temp;
        }
        
        return previous;
    }
}

 

1. 2021.01.12 시도

소요시간: 10분

class Solution {
    public boolean isPalindrome(ListNode head) {
        int count =0;
        ListNode countNode = head;
        while(countNode!=null) {
            count++;
            countNode = countNode.next;
        }

        int mid = count/2 ;
        ListNode gotoMiddleNode = head;
        ListNode prev = null;
        while(mid != 0) {
            mid--;
            ListNode temp = gotoMiddleNode.next;
            gotoMiddleNode.next = prev;
            prev = gotoMiddleNode;
            gotoMiddleNode = temp;
        }

        //홀수일때는 한칸 더 가서 비교점 시작.
        gotoMiddleNode = count%2==0 ? gotoMiddleNode: gotoMiddleNode.next;
        while(prev!= null) {
            if (prev.val != gotoMiddleNode.val) {
                return false;
            }
            prev = prev.next;
            gotoMiddleNode = gotoMiddleNode.next;
        }

        return true;
    }
}

풀이 접근 과정

중간을 찾고 비교를 해야한다.

데이터를 저장하면서 같은 숫자가 나왔을때 비교해볼 수 있겠다. 그러나 O(n) 공간이 들겠다.

n번 3번돌리면 찾을 수 있겠다. 처음에 숫자세고(1), 중간까지가고(2) 비교하기(3)

비교할때 순서가 같아야 하므로 2번중간까지 셀때 세면서 prev를 이용해 방향을 바꿔야겠다.

mid값이 홀수일때, 짝수일때를 생각해야한다.

 

느낀점

• linkedlist문제가 나오면 머리속이든, 손으로든 역시 그림을 그려서 푸는게 좋다.
• linkedlist는 공간의 사용없이 방향 변경이 가능하다는 사실을 기억해두자.
• 솔루션3번이 내 풀이와 같다. 결국 가운데 찾고 리버스하고 비교하기.
• 다른건 array로 복사해서 포인트 이용해서 따라가는거와 하나는 전역변수 써서 recurisve하게 푸는방법도 소개되었는데 이렇게 푸는게 제일 좋아보이긴한다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형