기술면접 알고리즘 [Linked List] : 링크드 리스트 스트링 비교 (Compare two strings represented as linked lists)

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.

각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다.

---

링크드 리스트 스트링 비교

string 을 링크드 리스트로 표현했다고 했을때, 다음과 같이 스트링을 비교하는 함수를 구현해 보자. 단, 투 포인터를 이용하여 순회한다.

#include <stdio.h>
#include <memory>
#include <iostream>

struct Node {
    char data;
    Node* next;
    Node(char data) : data{data}, next{nullptr} {}
};

struct List {
    List() : head{nullptr} {}
    
    void insert(char x) {
        Node* newNode = new Node(x);
        
        if (!head) {
            head = std::move(newNode);
            return;
        }

        newNode->next = head;
        head = newNode;        
    }
    
    int compare(List& a) {

        Node* left = this->head;
        Node* right = a.head;

        while (left && right) {

            if (left->data > right->data)
                return 1;
            else if (right->data > left->data)
                return -1;
            else {
                left = left->next;
                right = right->next;
            }

        }

        // if length are same
        if (!left && !right) {
            return 0;
        } else if (!left) {
            return -1;
        } else return 1;

    }

    friend std::ostream& operator<<(std::ostream &os, const List &list);
    
private:
    Node* head;
};

std::ostream& operator<<(std::ostream &os, const List &list) {
    Node* temp = list.head;

    if (!temp) {
        std::cout << "Linked list is empty" << std::endl;
        return os;
    }
    
    while (temp) {
        os << temp->data << " ";
        temp = temp->next;
    }
    os << std::endl;
    
    return os;
}

int main()
{
    List l;
    
    l.insert('1');
    l.insert('t');
    l.insert('u');
    l.insert('n');
    l.insert('h');
    l.insert('s');
    l.insert('a');
    l.insert('h');

    std::cout << l;


    List r;

    r.insert('2');
    r.insert('t');
    r.insert('u');
    r.insert('n');
    r.insert('h');
    r.insert('s');
    r.insert('a');
    r.insert('h');
    
    std::cout << r;

    std::cout << l.compare(r) << std::endl;

    
    return 0;
}