Week 4-1 : Linked List

< 180417 >

1) 연결리스트에서 특정 값을 찾는 함수.

ListNode* search(ListNode *head, int x)
{
    ListNode *p = head;
    while(p) {
        if(p->data == x) 
            return p;
        p = p->link;
    }
    return p; // p == NULL
}

>> main() 에서의 head 포인터가 가리키는 대상이 변경될 가능성이 없기 때문에..!! 싱글포인터 자체로 매개변수로 전달 받는다.

>> 찾는 값이 없으면 NULL 을 리턴한다.

2) 연결리스트에서 최대값을 갖는 노드와 마지막 노드 교환하기.

void changeMax(ListNode **phead)
{
    ListNode *prev=NULL, *cur=*phead;
    ListNode *pMax=NULL, *cMax=*phead;
 
    if(*phead == NULL) return ;
    
    while(cur->link != NULL) {
        if(cMax->data < cur->data) {
            cMax = cur;
            pMax = prev;
        }       
        prev = cur;
        cur = cur->link;
    }
    // Compare cMax with last Node
    if(cMax->data < cur->data) {
        cMax = cur;
        pMax = prev;
    }       
 
    // swap node
    pMax == NULL ? (cur->link = (*phead)->link) : (cur->link = pMax->link);
    pMax == NULL ? (*phead = cur) : (pMax->link = cur);
    prev->link = cMax;
    cMax->link = NULL;
}

>> 8 : cur->link != NULL 이라고 조건의 설정해야 cur 포인터가 마지막 노드를 가리키게 된다.

>> 23-26 : 노드를 스왑하는 과정이다. 그림을 그려가며 순서를 잘 파악한 다음 코드로 옮겨버릇하자.

>> 매개변수로는 더블포인터를 주었다. main() 에서의 head 포인터가 가리키는 노드가 변경될 수 있기 때문이다.

     (head 포이터가 가리키는 첫번째 노드가 최대값인 경우)

>> 가만 잘 생각해보면, 굳이 노드를 스왑할 필요는 없어보인다. 두 노드의 data만 swap 하면 되는데, 뭣하러 이리 어렵게 했나 싶다.

3) 두 개의 연결리스트 이어 붙이기.

- 교재의 있는 코드는 아래와 같다.

ListNode* concat(ListNode *head1, ListNode *head2)
{
    ListNode *p;
    if(head1 == NULL) return head2;
    if(head2 == NULL) return head1;
    
    p = head1;
    while(p->link != NULL) 
        p = p->link;
 
    p->link = head2;
    return head1;
}

>> 이전까진 별 생각이 없었는데, 다시보니 head1 == NULL 인경우, 이 함수가 종료가 되어도 head1 은 NULL 상태 그대로다.

>> 하지만, head1 != NULL 인 경우, 마지막 노드에 head2 가 가리키는 노드를 이어 붙인다음 head1 의 주소를 리턴한다.

     즉, 위의 경우 head1 의 변경이 없는데, 아래의 경우 head1 의 변경이 생긴다. 일관성이 없다.. 맘에 안든다;;

- 그래서 바꾸어 보았다. 무조건 head1 의 뒤에 이어붙여지는 결과가 될 수 있도록..!!

void concat(ListNode **head1, ListNode *head2)
{
    ListNode *p;
    if(head1 == NULL) { *head1 = head2; return ; }
    if(head2 == NULL) return ;
    
    p = *head1;
    while(p->link != NULL) 
        p = p->link;
 
    p->link = head2;
}

>> 8-9 : 루프를 빠져나가면 p는 마지막 노드를 가리키는 상태가 된다.

>> 예시는 아래와 같다.