단방향 링크드 리스트 뒤집기 (C/C++)

최근에 다들 이름만 들어도 알 회사에 면접을 볼 일이 있었다.

그 전, 입사 테스트로 단방향 링크드 리스트 뒤집기라는 과제를 받았었는데, 손으로 짜려다가 머리가 고장나버리는 바람에 제대로 완성을 못하고, 머릿속으로만 복기를 했었다가 면접때 해당 문제 다시풀기 라는 초유의 사태를 만나 그대로 면접에서 대형 사고를 치고 말았다..

 

물론 떨어졌고.

 

너무 아쉽긴 하지만 실수해서 망한건 이미 망한거고...

이왕 이렇게 된거, 복기도 좀 하고 다시는 같은 실수를 안하도록 코드 정리를 해서 올려보고자 한다.

 

---

 

우선, 단방향 리스트는 대충 다음과 같은 느낌으로 구현된다.

 

struct List
{
	List* next;
	int data;

	List(int newData)
	{
		data = newData;
		next = nullptr;
	}
};

 

그리고 이걸 뒤집으려면, 단순히 생각하면 전체를 순회하면서 한바퀴 돌면 그만.

 

 

 

그래서 처음 생각했던 (그리고 면접때까지 결국 제대로 못 구현했던) 방식은 다음과 같다.

 

우선, 링크드리스트가 "1,2,3,4,5"가 순서대로 있다는 가정하에 설명을 이어가도록 하겠다.

List* ReverseList(List* list)
{
	List* Result;
	List* InputList = list;

	//끝부분 인식
	while (true)
	{
		if (InputList->next->next == nullptr)
		{
			Result = InputList->next;
			InputList->next = nullptr;
			Result->next = InputList;

			break;
		}
		InputList = InputList->next;
	}

	//순서 뒤집기
	List* ResultNow = Result->next;
	InputList = list;
	while (InputList->next != nullptr)
	{
		
		while (true)
		{		
			std::cout << InputList->data << std::endl;
			if (InputList->next->next == nullptr)
			{
				ResultNow->next = InputList;
				InputList->next = nullptr;
				ResultNow = ResultNow->next;

				InputList = list;
				break;
			}
			InputList = InputList->next;
		}
	}
	return Result;
}

 

굉장히... 길다.

 

로직을 간단히 설명하면, 먼저 링크드 리스트의 맨 마지막인 5를 찾고,

그 다음부터는 "뒤가 존재하지 않는 노드" 를 뒤집을 리스트의 끝에 집어 넣는 방식이다.

 

즉,

 

처음 While문 종료시

원본 리스트 :  1->2->3->4->5

뒤집은 리스트 : 5->4

뒤집힐 리스트 : 1->2->3->4

 

해당 상태가 되는데,

 

두번째 While문에서부터는 본인 노드의 다음 다음 노드가 비어있을때 본인을 집어넣는 방식으로 이루어진다.

 

그래서, 위와같이 4가 마지막인것이 2개가 존재하는것이 의도적인 작업인데, 이를 면접때 제대로 대답을 하지 못한게 좀 치명적인 실수였다고 생각이 든다...

 

여튼, 두번째 While문에서는 My->Next->Next == nullptr 일때, My를 집어넣는식으로 이루어진다.

 

물론, 당연히 결과는 잘 나온다.

 

하지만, 시간 복잡도 상으로는 O(n+n²) 라는... 좀 느린 수준의 코드고, 좀 어거지로 짠 느낌이 없잖아 있다.

 

 

우선, while 순회를 1개 블럭으로 줄여보자.

 

별 거 없다, 두개 합치면 그만이다.

List* ReverseList(List* list)
{
	List* Result = nullptr;
	List* ResultNow = nullptr;
	List* InputList = list;


	//순서 뒤집기
	InputList = list;
	while (InputList->next != nullptr)
	{		
		while (true)
		{		
			//std::cout << InputList->data << std::endl;
			if (InputList->next->next == nullptr)
			{
				if (Result == nullptr)
				{
					Result = InputList->next;
					InputList->next = nullptr;
					Result->next = InputList;
					ResultNow = Result->next;
				}
				else
				{
					ResultNow->next = InputList;
					InputList->next = nullptr;
					ResultNow = ResultNow->next;

				}
				InputList = list;
				break;
			}
			InputList = InputList->next;
		}
	}
	return Result;
}

어차피 if의 조건은 List->next->next == nullptr 로 동일하기 때문에 두개의 While을 하나로 합칠 수 있다.

 

하지만 이래도 O(n²) 의 시간복잡도가 나온다.

더 줄여보자.

 

: 해당 로직은 다음 블로그를 참고하였습니다 : 

https://seongonion.tistory.com/78

단방향 링크드 리스트 뒤집기 - 파이썬 (Python)

 

 

해당 블로그의 내용을 요약하면...

이전 위치, 현재 위치, 다음 위치를 기억하고 뒤집어가면서 진행하기 정도로 요약가능하다.

 

다음 위치를 진행 시키면서, 현재 위치의 다음 방향을 이전 위치로 기록하면서 진행하면 OK.

 

List* ReverseList(List* list)
{
	List* Result = nullptr;
	//순서 뒤집기
	List* prev = nullptr;
	List* temp = list->next;
	List* now = list;

	while (now != nullptr)
	{
		now->next = prev;
		if (temp == nullptr)
		{
			Result = now;
			break;
		}
		prev = now;
		now = temp;
		temp = temp->next;		
	}
	return Result;
}

 

이번에도 잘 나온다.

 

코드도 훨씬 깔끔하고 간결해져서, 가독성 측면에선 이쪽이 훨씬 나아보임.

 

 

 

 

..이라는 복기를 좀만 일찍했으면 좋았을걸~ 싶은 생각이 든다.