[Linked Lists] Compare two linked lists

난이도: ★☆☆☆☆ • solved on: 2025-11-06

---

문제 요약

• 문제 유형: 연결 리스트(Linked List), 비교(Comparison)
• 요구사항: 두 개의 단일 연결 리스트가 주어졌을 때, 두 리스트의 길이와 각 노드의 데이터가 동일한지 판별하여
  동일하면 true, 다르면 false를 반환해야 한다.

---

사용 개념

1. 자료구조

   • SinglyLinkedListNode: 단일 연결 리스트의 노드 구조체
     (data 값과 next 포인터를 가짐)

2. 알고리즘/기법

   • 반복문을 이용한 리스트 동시 순회
   • 조건문을 통한 비교 연산 및 null 검사

3. 핵심 키워드

   • 연결 리스트 비교
   • 동기화 순회 (Simultaneous traversal)
   • 길이 및 데이터 일치 검증

---

풀이 아이디어

1. 문제 분해

• 두 연결 리스트의 첫 노드부터 동시에 순회하면서 data를 비교한다.
• 두 노드 중 하나라도 null에 먼저 도달하거나 data 값이 다르면 false를 반환한다.

2. 핵심 로직 흐름

   while (head1 != null && head2 != null):
       if (head1.data != head2.data):
           return false
       head1 = head1.next
       head2 = head2.next
   
   // 반복문 종료 후, 둘 다 null이어야 true
   if (head1 != head2):
       return false
   else:
       return true

3. 예외 처리

   • 두 리스트 중 하나만 null일 때 → 길이가 다르므로 false 반환
   • 두 리스트가 모두 비어 있는 경우 → true 반환

---

코드

static boolean compareLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    SinglyLinkedListNode headOneCurrent = head1;
    SinglyLinkedListNode headTwoCurrent = head2;

    while (headOneCurrent != null && headTwoCurrent != null) {
        if (headOneCurrent.data != headTwoCurrent.data) {
            return false;
        }
        headOneCurrent = headOneCurrent.next;
        headTwoCurrent = headTwoCurrent.next;
    }

    if (headOneCurrent != headTwoCurrent) {
        return false;
    } else {
        return true;
    }
}

---

시간·공간 복잡도

• 시간 복잡도: O(N) — N은 두 리스트 중 더 짧은 길이
• 공간 복잡도: O(1) — 추가 자료구조 사용 없음

---

어려웠던 점

• 두 리스트가 모두 null이 아닌데, 한쪽만 먼저 끝나는 경우를 처음에 고려하지 않아 길이 불일치 케이스에서 오답이 발생했다.
  (headOneCurrent != headTwoCurrent 검사 추가로 해결)

---

배운 점 및 팁

• 연결 리스트 비교 시 종료 조건 설정이 핵심이다.
  → 단순히 값만 비교하면 안 되고, 리스트 길이 일치 여부도 꼭 확인해야 한다.
• while 루프 이후 head1 != head2 조건으로 길이 차이를 간단히 판별할 수 있다.
  (두 포인터 중 하나만 null이면 false)

---

참고 및 링크

• 문제 링크: https://www.hackerrank.com/challenges/compare-two-linked-lists/problem
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천):

  • [Baekjoon 1929] 연결 리스트의 합 (두 리스트 병합)
  • [HackerRank] Merge two sorted linked lists

• 확장 문제 (GPT 추천):

  • 두 연결 리스트가 교차하는 지점 찾기
  • 연결 리스트의 회문 여부 판단 (Palindrome Linked List)