128일 (234. Palindrome Linked List) LinkedList, 리스트 조작

Given the head of a singly linked list, return true if it is a 

palindrome

 or false otherwise.

 

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

 

Constraints:

• The number of nodes in the list is in the range [1, 10^5].
• 0 <= Node.val <= 9

 

Follow up: Could you do it in O(n) time and O(1) space?

 

 

- 접근방법

 

시간복잡도는 O(n)으로 특히 공간복잡도를 O(1)에서 문제를 풀려면 주어진 연결리스트를 조작하여 푸는 방법 밖에 생각이 나지 않았다.

 

1. 먼저 연결리스트의 길이가 짝수인지 홀수인지 판별한다.

 

(1) 연결리스트가 1-2-3-4-5-6 (짝수) 라면?

→ mid는 1-2-3을 순차적으로 가리키며, end는 1-3-5를 순차적으로 가리키며 반복문이 종료된다.

 mid는 3을 가리키므로 (123 / 456) mid = mid.next로 다음 노드인 4를 가리켜야한다.(123 / 456)

그래야 456에 해당하는 노드를 역순으로 조작하여 (123 / 654) 각각 (1,6) (2,5) (3,4)의 값을 비교하며 회문임을 판별한다.

 

(2) 연결리스트가 1-2-3-4-5 (홀수) 라면?

→ mid는 1-2-3을 순차적으로 가리키며, end는 1-3-5를 순차적으로 가리키며 반복문이 종료된다.

mid는 12345에서 3을 가리키므로, 345를 역순으로 조작하여 (543), 각 노드를 123과 비교하며 회문임을 판별한다.

 

 

2. mid의 위치부터 연결리스트를 역순으로 조작한다.

→  {1,2,5,2,1}이라면 head = {1,2,5}가 되며 reverseHead = {1,2,5}가 된다.

→  {1,2,5,4,3}이라면 head = {1,2,5}가 되며 reverseHead = {3,4,5}가 된다.

 

 

3. head와 reverseHead의 시작노드부터 끝까지 각 노드의 값을 비교하여 모두 같은 값이라면 true, 아니라면 false를 리턴.

 

 

- 코드

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode mid = head;
        ListNode end = head;
        ListNode reverseHead = null;

        while(true) { // 1.
            if(end.next != null && end.next.next == null) {
                mid = mid.next;
                break;
            }
            else if(end != null && end.next == null) break;

            mid = mid.next;
            end = end.next.next;
        }

        while(mid != null) { // 2.
            ListNode nextNode = mid.next;
            mid.next = reverseHead;
            reverseHead = mid;
            mid = nextNode;
        }

        while(head != null && reverseHead != null) { // 3.
            if(head.val != reverseHead.val) return false;
            head = head.next;
            reverseHead = reverseHead.next;
        }

        return true;
    }

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

 

코드가 긴 것 같지만 접근방법 3개에 해당하는 반복문 3개를 구현하면 끝이다.

연결리스트의 길이가 짝수인가 홀수인가에 따라서 반절로 자른 후, 나머지 반절을 역순으로 연결하여 새로운 연결리스트를 만들고, 기존 연결리스트 반쪽과 비교하는 코드이다.

 

 

 

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

LeetCode - The World's Leading Online Programming Learning Platform