# Merge two sorted linked lists (Linked Lists)
[문제]
[코드]
/*
class SinglyLinkedListNode {
public:
int data;
SinglyLinkedListNode *next;
SinglyLinkedListNode(int node_data) {
this->data = node_data;
this->next = nullptr;
}
};
class SinglyLinkedList {
public:
SinglyLinkedListNode *head;
SinglyLinkedListNode *tail;
SinglyLinkedList() {
this->head = nullptr;
this->tail = nullptr;
}
void insert_node(int node_data) {
SinglyLinkedListNode* node = new SinglyLinkedListNode(node_data);
if (!this->head) {
this->head = node;
} else {
this->tail->next = node;
}
this->tail = node;
}
};
*/
SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
SinglyLinkedList *list = new SinglyLinkedList();
while(head1 && head2)
{
if(head1->data <= head2->data)
{
list->insert_node(head1->data);
head1 = head1->next;
}
else
{
list->insert_node(head2->data);
head2 = head2->next;
}
}
for(; head1; head1 = head1->next) list->insert_node(head1->data);
for(; head2; head2 = head2->next) list->insert_node(head2->data);
return list->head;
}
[코드설명]
두 개의 sorted linked list를 merge하는 문제다.
merge sort 알고리즘을 사용해서 해결했다.merge된 linked list를 구현하기 위해 새로운 list를 만들었다. (list)
linked list를 merge하기 위해 sorted linked list의 끝에 도달하기 전까지 while문을 돌게 했다.
while loop안에서 head1->data와 head2->data를 비교하고 더 작은 값을 llist에 추가했다. (insert_node 메소드 사용)
while loop을 벗어난 후에는 아직 남아 있는 data를 추가하기 위해 for문으로 남은 data를 추가하게 만들었다.
마지막엔 list의 head를 반환한다.
[채점 결과]
# Get Node Value (Linked Lists)
[문제]
[코드]
SinglyLinkedListNode* reverse(SinglyLinkedListNode* llist) {
SinglyLinkedList *list = new SinglyLinkedList();
for(; llist; llist = llist->next)
list->insert_node(llist->data);
if(!(list->head)) return list->head;
SinglyLinkedListNode *two = NULL, *three, *temp = list->head;
do{
three = two;
two = temp;
temp = temp->next;
two->next = three;
} while(temp);
return two;
}
int getNode(SinglyLinkedListNode* llist, int positionFromTail) {
SinglyLinkedListNode *temp = reverse(llist);
int i = 0;
while(i != positionFromTail)
{
temp = temp->next;
i++;
}
return temp->data;
}
[코드설명]
연결리스트에서 지정된 위치의 data를 출력하는 문제다. 이때 위치는 tail을 기준으로 0이다.
tail부터 0으로 세기 때문에 연결리스트를 reverse해서 새로 만들었다.
reverse 함수는 반대로 연결된 새로운 연결리스트를 만드는 함수다.list에 llist의 node를 그대로 복사했다.그 후 list의 head가 NULL이면 그대로 head를 return하고, 아니라면 아래의 do-while문으로 reverse한다.two와 three가 링크를 따라 움직이면서 next를 반대로 변경해준다.while문을 벗어났을 때 two가 reverse된 list의 head이므로 two를 반환한다.
getNode함수에서 reverse함수로 반대로 연결한 연결리스트의 head pointer를 가져온다.head pointer를 temp에 담고, i가 positionFromTail과 같아질 때까지 temp는 링크를 따라 이동한다.while loop을 벗어났을 때의 temp가 positionFromTail에 있는 노드이므로 temp->data를 반환한다.
[채점 결과]
