[Jungle][TIL] 240416 Linked List - (2)

frontBackSplitLL(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
연결리스트를 반으로 분할하는 함수
예시) 2, 3, 5, 6, 7 => frontList: 2, 3, 5, backList: 6, 7
홀수개이면 extra 남는 요소는 첫번째 리스트로 간다.

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList) 
{
	//분할 기준이 되는 노드의 시작을 가리키는 포인터
	ListNode *front = ll->head;
    //분할을 위해 2스텝씩 이동하며 연결리스트 순회 
    ListNode *back = ll->head;
	//front의 이전 노드를 가리키는 포인터 
    ListNode *prev; 
  
    //back이 null이 아니고, back의 다음 노드도 null이 아닐 때까지 반복
    while (back != NULL && back -> next != NULL ) {
  	
    	prev = front;
        //front는 한칸씩 이동
        //back은 2칸씩 이동하여 
        //리스트의 중간 지점을 찾는다. 
    	front = front->next;
        back = back->next->next; 
    }
   
    //연결 리스트에 노드가 하나 이상인 경우
    if (prev!= NULL) {
    	//back is not null
        //LL노드 개수가 홀수라면 
    	if (back!=NULL) {
    		resultBackList-> head = front->next; 
    		prev->next-> next =NULL;
            resultFrontList->head = ll-> head; 
  
    	}
        //back is null
        //LL의 노드수가 짝수라면 
       	else {
        	prev->next = NULL;
            resultFrontList->head= ll->head;
            resultBackList->head = front; 
        }
	}
}

moveMaxToFront(ListNode **ptrHead)
: 최댓값을 맨 앞으로 이동시키는 함수
예시: 30, 20, 40, 70, 50 => 70, 30, 20, 40, 50

int moveMaxToFront(ListNode **ptrHead) 
{
	//최댓값을 갖는 이전 노드를 가리키는 포인터
	ListNode *maxNodePrev;
    maxNodePrev = NULL;
    
    //연결리스트를 순회할 임시 포인터
    ListNode *temp;
    temp = *ptrHead;
    
    //최댓값을 가진 노드를 가리키는 포인터 
    ListNode *maxNode;
    maxNode = *ptrHead; 
    
    if (*ptrHead == NULL || (*ptrHead) -> next ==NULL) {
    	return;
    }
    
    //연결 리스트를 순회
    while(temp->next != NULL) {
    	//다음 노드의 item이 최댓값을 담은
        // 리스트의 item보다 값이 크다면 
        // 최댓값 갱신 
        if (temp -> next-> item > maxNode->item) {
        	//최댓값을 가진 이전 노드 저장 
			maxNodePrev = temp;
            //최댓값을 가진 노드 갱신 
            maxNode = temp -> next; 

		}
        temp = temp-> next; // 다음 노드로 이동 
    }
    
    	//이동 작업
    if (maxNodePrev != NULL) {
    //최댓값의 이전 노드와 그 다음 노드를 연결
    	maxNodePrev -> next = maxNode -> next;
    	//최댓갑을 가진 노드를 맨 앞으로 이동 
        maxNode -> next = *ptrHead; 
    	*ptrHead = maxNode; 
        //연결리스트의 헤드 포인터를 
        //최댓갑을 가진 노드로 

	}
}

RecursiveReverse(ListNode **ptrHead)
1, 2, 3, 4, 5-> 5, 4, 3, 2, 1
재귀적으로 연결리스트의 값들을 역순으로 바꾸기

void RecursiveReverse(ListNode **ptrHead)
{ 	
	//현재 노드를 포인터로 설정 
	ListNode *cur = *ptrHead; 
	
    //현재 노드의 다음 노드
    ListNode *rest = cur -> next;
   
    if ((*ptrHead) == NULL || (*ptrHead) -> next == NULL) {
    	return ; 
    }
	
   
    RecursiveReverse(&rest); 
   
    //현재 노드의 다음 다음 노드와 연결시킨다.
    // 순서를 바꾸기 위해 
    cur->next->next = cur; 
   
    //현재 노드의 다음 노드를 NULL로 설정하여
    //연결 리스트의 끝을 표시
    cur -> next = NULL;
	
    // 연결 리스트의 ptrHead를 재귀적으로 뒤집은 
    // 리스트의 헤드(rest)로 업데이트 
	*ptrHead = rest ; 
}
``

예시)

1->2->3->4->NULL

ptrHead가 가리키는 것: 1 -> 2 -> 3 -> 4 -> NULL
함수 호출: RecursiveReverse(&ptrHead)

cur: 1 (현재 노드)
rest: 2 -> 3 -> 4 -> NULL (현재 노드의 다음 노드)
RecursiveReverse(&rest)

cur: 2 (현재 노드)
rest: 3 -> 4 -> NULL (현재 노드의 다음 노드)
RecursiveReverse(&rest)

cur: 3 (현재 노드)
rest: 4 -> NULL (현재 노드의 다음 노드)
RecursiveReverse(&rest)

cur:4 (현재 노드)
rest: NULL (현재 노드의 다음 노드)
-> 재귀 종료

cur->next->next = cur; 실행
4 -> NULL을 4 -> 3으로 변경
cur->next = NULL;

3 -> 4를 3 -> NULL로 변경하여 연결 리스트의 끝을 표시

*ptrHead = rest;

ptrHead가 가리키는 헤드 포인터를 4로 업데이트
연결 리스트의 새로운 헤드를 설정