C# 프로그래밍 기초 실습 전자책

C# / .NET 알고리즘과 퀴즈
본 알고리즘 퀴즈 문제는 C#/.NET 개발자를 위한 알고리즘 인터뷰 혹은 C# 프로그래밍을 통한
문제 해결 알고리즘을 연구해 보는데 도움이 되고자 작성되었습니다.


퀴즈 질문


예상답변/설명

가장 단순하게는 Singly Linked List를 읽어 가면서 반대 방향으로 복제된 새로운 리스트를 만드는 것을 생각할 수 있다. 하지만, 이 방식은 Linked List의 크기에 비례하여 별도의 메모리를 필요로 한다는 점에서 효율적이지 않다.

따라서, 해당 Linked List의 포인터만을 반대로 변경하는 방식이 효율적인데, 이를 구현하는 방식으로 아래와 같이 Recursive를 이용한 방식과 순차적인 Iterative 방식을 생각해 볼 수 있다.

class SList
{
    public int Value;
    public SList Next;
    public SList(int val) {
        this.Value = val;
    }
}

// Recursive 접근
// CALL : var rev = ReverseRecursive(null, slist);
static SList ReverseRecursive(SList prev, SList curr)
{
    SList next = curr.Next;
    curr.Next = prev;

    if (next == null)
        return curr;
    else
        return Reverse(curr, next);
}

// Iterative 접근
// CALL : var rev = ReverseList(slist);
static SList ReverseList(SList list)
{
    SList h = list, p = null, q = list;

    while (h != null)
    {
        h = h.Next;                
                
        q.Next = p;
        p = q;

        if (h != null) q = h;                
    }

    return q;
}