[Leetcode] 143. Reorder List

Identifying the Problem

주어진 linked list를 규칙에 맞게 재 정렬한다.
list가 L0 → L1 → … → Ln - 1 → Ln 순이라면
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 순으로 재 정렬

Organizing thoughts

MAIN :  메인은 중간까지는 정순, 중간 이후부터 list를 뒤집고,

            이후 왼쪽과 오른쪽 끝에서 중간으로 규칙대로 연결한다.

 

1. list의 가운데 주소 찾기 

    1.0 가운데의 next는 NULL이 되어야 한다.
2. 가운데 주소 이후부터 가운데 주소 다음까지 뒤집기
3. 양끝의 주소를 알아내고
4. 양끝부터 연결 시작

   4.0 1번 주소 저장
   4.1 0번과 n번 연결
   4.2 n-1번 주소 저장
   4.3 n번과 1번 연결
   4.4 2번 주소 저장

   …. 이런 식으로 계속

 

Sourcecode

struct ListNode* find_mid(struct ListNode* node);
struct ListNode* reverse(struct ListNode* node); 

void reorderList(struct ListNode * head)
{	
    struct ListNode* left = head; //왼쪽
	struct ListNode* mid = find_mid(head); //중간	
	struct ListNode* right = reverse(mid); //중간부터 끝까지 배열을 뒤집는다.
    
    mid->next = NULL;
    
    struct ListNode* left_tmp = head;
	struct ListNode* right_tmp = right;
    
    while(!(left == mid && right == mid))	
    {		
        left_tmp = left;		
        left = left->next; 		
        left_tmp->next = right;
        
        
		right_tmp = right;		
        right = right->next;	 		
        if(right==NULL) break; 
        //list가 짝수 개인 경우 마지막 반복에서 무한순회가 나게끔 고리가 형성된다.
        //이러한 오류를 막기위해 해당 조건문을 작성했다.
        right_tmp->next = left;	
    }
	
 }

struct ListNode* find_mid(struct ListNode* node)
{
	struct ListNode* fast = node;
	struct ListNode* slow = node;

	while( !(fast == NULL || fast->next == NULL))	
    {	
        
        fast = fast->next->next;		
        slow = slow->next;
	}		
    
    return slow;
}
struct ListNode* reverse(struct ListNode* node)
{
	struct ListNode* newHead = NULL;	
    
    while(node)	
    {
		struct ListNode* tmpNode = node -> next;		
        node->next = newHead;		
        newHead = node;		
        node = tmpNode;	
	}

	return newHead;
}