LeetCode 234번 - Palindrome Linked List

문제

주어진 연결 리스트가 회문 구조인지 확인하는 문제이다.

---

살펴보기

문제를 보고 가장 먼저 생각난 방법은 리스트를 이용하는 방법이었다.

 

리스트를 만들어 노드값을 전부 저장한 후, 반복문을 이용해 리스트의 양끝에서부터 가운데로 순회하면서 양쪽의 값을 비교해 회문인지 확인하는 방법이다.

 

그래서 우선 리스트를 이용해 문제를 푼 다음, 206번 문제를 풀 때 배운대로 뒤집힌 연결 리스트를 만든 후 원본 연결 리스트랑 비교하는 방식으로 풀어보았다.

 

 

 

의도했던 대로 문제를 풀긴 했지만.. 더 좋은 풀이가 있는걸 알게 되어서 풀이를 참고해 한번 더 풀어보았다.

 

우선 두 개의 포인터를 이용해, 연결 리스트의 중간 지점을 찾아야 한다.

 

160번 문제에서 했던 것처럼 한 포인터(slow)는 한 번에 한칸씩만 이동하고, 다른 포인터(fast)는 한 번에 두 칸씩 이동시킨다.

 

fast 포인터가 더 이상 이동할 수 없을 때까지 두 포인터를 이동시키고 나면, slow 포인터는 연결 리스트의 중간 지점쯤에 위치하게 된다.

 

(구체적으로는, 연결 리스트의 길이가 홀수이면 정중앙, 짝수이면 (연결 리스트의 길이/2)번째 노드에 위치하게 된다.)

 

이제 slow 포인터의 다음 노드부터 복사해 뒤집힌 반쪽짜리 연결 리스트를 만들고, 이 연결 리스트가 끝날 때까지 원본 연결 리스트와 비교하면 된다!

 

그리고 문제를 풀면서 알게되었는데.. 연결 리스트를 뒤집을 때 어떤 방식으로 뒤집는지에 따라서도 성능이 많이 바뀌었다.

 

ListNode reverse = null;

while(slow != null){
    ListNode curr = new ListNode(slow.val);
    slow = slow.next;
    curr.next = reverse;
    reverse = curr;
}

처음에 뒤집힌 연결리스트를 만들 때 위와 같은 방법으로 만들었다.

 

1. 뒤집힌 연결 리스트를 연결할 노드를 만든다.

2. 주어진 연결 리스트(slow)의 노드값과 동일한 값을 가진 노드를 만든다.

3. 주어진 연결 리스트를 한 칸 순회시킨다.

4. 2번에서 만든 노드의 뒤에, 1번에서 만든 노드를 연결한다.

5. 1번에서 만든 노드의 주소값으로 2번 노드의 주소값을 대입한다..

 

이런 식으로 뒤집었었는데

 

ListNode reverse = null;
ListNode curr = slow.next;

while(curr != null){
    ListNode temp = curr.next;
    curr.next = reverse;
    reverse = curr;
    curr = temp;
}

참고한 풀이에서는 위와 같은 방법으로 뒤집고 있었다..

 

1. 뒤집힌 연결 리스트를 연결할 노드를 만든다(ListNode reverse)

2. slow 포인터가 가리키는 노드의 다음 노드를 가리키는 노드를 만든다.(ListNode curr)

3. 임시 노드를 만들어, curr의 다음 노드를 참조하게 한다.

4. curr의 다음 노드가 reverse를 참조하게 한다.

5. reverse가 curr를 참조하게 한후..

6. curr가 temp를 참조하게 한다. 여기서 temp는 curr가 원래 가리키고 있던 노드이다.

 

다양한 방법으로 뒤집을 수 있도록 연습해야겠다.

---

풀어보기

1. 리스트를 이용한 방법

List<Integer> list = new ArrayList<>();

while(head!=null){
    list.add(head.val);
    head = head.next;
}

int start = 0;
int end = list.size() - 1;

while(start < end){
    if(list.get(start++) != list.get(end--)) return false;
}

return true;

 

2. 뒤집힌 연결 리스트를 이용한 방법

ListNode newHead = head;
ListNode reverse = new ListNode();

while(newHead != null){
    ListNode curr = new ListNode(newHead.val);
    newHead = newHead.next;
    curr.next = reverse;
    reverse = curr;
}

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

return true;

 

3. 2번 개선

if(head == null) return true;

ListNode slow = head;
ListNode fast = head;

while(fast.next != null && fast.next.next != null){
    slow = slow.next;
    fast = fast.next.next;
}

ListNode reverse = null;
ListNode curr = slow.next;

while(curr != null){
    ListNode temp = curr.next;
    curr.next = reverse;
    reverse = curr;
    curr = temp;
}

while(reverse!=null){
    if(reverse.val != head.val) return false;
    reverse = reverse.next;
    head = head.next;
}

return true;

 

3번째 방법의 코드가 제일 길고, 1번째 방법의 코드가 제일 짧지만..

속도는 오히려 3번째 방법이 제일 빨랐고 1번째 방법이 제일 느렸다.