[Jungle][TIL] 240415 Linked List - (1)

LinkedList

• 구조체, struct

typedef struct _listnode{
	int item;
    struct _listnode *next;
} ListNode; 

typedef struct _linkedList{
	int size; 
    ListNode *head;
} LinkedList;

insertSortedLL(LinkedList *ll, int item)
연결리스트에 오름차순으로 정수를 삽입하는 함수

• 현재 연결 리스트에 삽입하려는 정수가 이미 리스트에 존재한다면 삽입하지 않는다.
  -> int item 중복 확인
• 연결 리스트 안에 값이 없다면
  -> 오름차순으로 삽입하려는 정수가 들어갈 index에 맞게 ListNode 삽입

int insertSortedLL(LinkedList *ll, int item) 
{
	// 현재 index 
	int curindex;
    curindex = 0;
   
    ListNode *cur;
    cur = ll-> head;
  
    //연결 리스트에 값이 없으면 
    if (ll == NULL)
    	return -1;
  	else 
    { 
    	//현재의 노드에 값이 있고,
        // 현재 노드의 item이 삽입하려는 item 보다 작거나 같으면
    	while (cur != NULL && cur -> item <= item) { 
        //	 중복된 값이 이미 있다면 
        if (cur-> item == item) {
        	return -1; 
        }
        // 현재 노드의 item이 삽입하려는 item 보다 작다면 
      	else {
			cur = cur-> next; 
			curindex = curindex + 1 ;
		} 
    }
    insertNode(ll, curindex, item);
    return curindex; 
  }
 

alternateMergeLL(LinkedList *ll1, LinkedList *ll2)
2번째 Linked List의 노드들은 1번째 Linked List의 사이사이에 삽입된다.

---

예시)
LinkedList1: 1, 2, 3
LinkedList2: 4, 5, 6, 7 이면

결과
LinkedList1: 1, 4, 2, 5, 3, 6,
LinkedList2: 7 이 된다.

LinkedList1의 노드들이 더 많은 경우에는
LinkedList2는 empty가 된다.

---

void alternateMergeLL(LinkedList *ll1, LinkedList *ll2) 
{
	int idx = 1;

	ListNode *ptrNode1;
	ListNode *ptrNode2;

	//l1l 헤드 노드를 가리키는 포인터 ptrNode1
	//ll2 헤드 노드를 가리키는 포인터 ptrNode2 
   
	ptrNode1 = ll1-> head;
	ptrNode2 = ll2->head; 
   
	// ptrNode2 가 NULL이 아닐 때 까지 반복 
	while (ptrNode2 != NULL ) {
    	// ll1 마지막 노드일 경우 반복을 멈춘다. 
        if (findNode(ll1, idx-1) == NULL)
        	break;
           
        insertNode(ll1, idx, ptrNode2 -> item);
       
        //삽입했으니 ptrNode2 다음 노드로 이동하고
        // ll2에서는 삭제하고 idx +=2 를 하여 이동한다. 
        ptrNode2 = ptrNode2 -> next;
        removeNode(ll2, 0);
        idx +=2; 
    }
}

moveOddItemsToBackLL
홀수의 값들은 연결리스트의 뒷 부분으로 이동시킨다.
예시)
2, 3, 4, 7, 15, 18 이라면
2, 4, 18, 3, 7, 15로 홀수들을 이동시킨다.

void moveOddItemsToBack(LinkedList *ll)
{
	ListNode *cur = ll->head;
    ListNode *prev = NULL;

	 if (ll == NULL) {
        return; 
    }

	// 홀수 값을 가진 노드들의 연결 리스트 head
    ListNode *oddHead = NULL; 
	// 홀수 값을 가진 노드들의 연결 리스트 tail 
    ListNode *oddTail = NULL; 
	// 짝수 값을 가진 노드들 중 가장 마지막 노드를 가리키는 포인터 
    ListNode *evenTail = NULL; 
	

    while (cur != NULL) {
		// 다음 노드를 가리키는 포인터 nextNode 
    	ListNode *nextNode = cur->next;

		// 현재 노드의 item이 홀수인 경우
        if (cur->item % 2 != 0) {

			//홀수 노드들의 연결 리스트들의 oddHead가 NULL이라면 
            if (oddHead == NULL) {
                oddHead = cur;
                oddTail = cur;
            } 
			//oddhead가 NULL이 아니라면 -> 이미 홀수값이 나왔었더라면
			//홀수 값을 가진 노드들 연결리스트의 꼬리의 next 가 cur
			else {
                oddTail-> next = cur;
				oddTail = cur;
            }

			//홀수를 갖는 리스트의 next는 NULL; 
            oddTail -> next = NULL;

			// 이전 노드를 가리키는 prev가 
			// NULL이 아니라면
            if (prev != NULL) {
                prev->next = nextNode;
            } 
			else {
                ll->head = nextNode;
            }
        } 
		// 현재 노드의 item이 짝수인 경우
		else {
            prev = cur;
			//짝수 tail이 null 이거나 prev->item 이 짝수라면
            if (evenTail == NULL || prev->item % 2 == 0) {
                evenTail = prev;
            }
        }

        cur = nextNode;
    }


    // 짝수 값을 가진 노드들의 끝에 홀수 노드들을 연결
	//evenTail이 null이 아니라면 
    if (evenTail != NULL) {
        evenTail->next = oddHead;
    } 
	//evenTail의 값이 NULL이라면
	//짝수 값이 없었던 경우
	else {
        ll->head = oddHead;
    }
}

Linkedlist에 대한 개념 + c언어 구현 능력 모두 부족한 상태,,,,
당연함. c 언어 처음해본다.
앞으로 정글에서 매일 매일 공부해서 성장하길 바라본다.
이번주 과제 화이팅,,