# Inserting a Node Into a Sorted Doubly Linked List (Linked Lists)
[문제]
[코드]
DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* llist, int data) {
DoublyLinkedListNode *node = new DoublyLinkedListNode(data);
DoublyLinkedListNode *temp = llist;
DoublyLinkedListNode *prev;
if(llist == NULL)
return node;
if(data <= temp->data)
{
node->next = temp;
temp->prev = node;
llist = node;
}
else
{
while(temp = temp->next)
{
prev = temp;
if(data <= temp->data)
{
node->prev = temp->prev;
node->next = temp;
temp->prev->next = node;
temp->prev = node;
break;
}
}
if(temp == NULL)
{
node->prev = prev;
prev->next = node;
}
}
return llist;
}
[코드설명]
doubly sorted linked list에 노드를 삽입하는 문제다.
먼저 empty list인지 확인한다. empty list가 맞다면 새로 삽입할 node의 포인터를 반환한다.
empty list가 아니라면 첫 번째 노드와 삽입할 노드의 data를 비교한다.
삽입할 data가 더 작다면 해당 위치에 삽입하고 llist(head)를 node로 변경한다.
첫 번째 노드보다 크다면 다음 노드들과 data를 비교하고 적절한 위치에 삽입한다.
data가 제일 큰 경우 list의 맨 마지막에 삽입한다.
최종적으로 llist(head)를 반환한다.
[채점 결과]
# Delete duplicate-value nodes from a sorted linked list (Linked Lists)
[문제]
[코드]
SinglyLinkedListNode* removeDuplicates(SinglyLinkedListNode* llist) {
if(llist == NULL) return llist;
SinglyLinkedListNode *temp = llist->next, *prev = llist, *del;
int duplicate = llist->data;
while(temp)
{
if(duplicate == temp->data)
{
del = temp;
temp = temp->next;
prev->next = temp;
free(del);
}
else
{
duplicate = temp->data;
prev = temp;
temp = temp->next;
}
}
return llist;
}
[코드설명]
sorted linked list에서 중복된 값을 삭제하는 문제다.
먼저 list가 empty인지 확인한다.
empty가 아니라면 두 번째 노드부터 시작해서 이전 노드와 중복된 값인지 확인한다.
중복이라면 해당 노드를 삭제한다.
중복이 아니라면 duplicate와 prev를 변경해서 비교를 위한 값을 바꾸고 다음 노드로 넘어간다.
[채점 결과]
