Leetcode - 24. Swap Nodes in Pairs

문제

주어진 링크드 리스트에서 한 pair씩 swap해라.

Input: head = [1,2,3,4]
Output: [2,1,4,3]

https://leetcode.com/problems/swap-nodes-in-pairs/

해결 아이디어 (iterative)

• first, second노드를 지정하고 swap. 이것을 두칸식 반복하는게 기본 아이디어. 어려웠다ㅇㅇ. 비슷하게는 풀다가 답이 안나와서 솔루션 슬쩍 참고함.
• first->next는 second->next를 가리키면 됨. 즉 1번 노드가 3을 가리키면 됨. 굳이 여기서 다음스텝의 swap이후 위치인 4를 가리킬 필요 없음. (나는 이 부분을 틀림)
• 한번에 두개씩 해결해 나가야함. (요게 핵심)
• prev노드는 이전의 first가 되며, 현재의 second를 가리켜야함.
• 생각해보면 그림대로 노드의 링크를 연결하면 되긴함..
• prev는 NULL로 시작했기 때문에 prev가 NULL이면 newhead = second로 초기화.
• 추가로 변수명을 잘 지어야한다는 사실을 또한번 깨달음. 변수명을 잘못지으면 인지부하가 급격히 증가한다. first, second로 지으니 인지부하가 확 줄어드는게 느껴짐.
• Leetcode 해설
  • 1
    
  • 2
    
  • 3
    

해결 iterative

struct ListNode* swapPairs(struct ListNode* head){
    struct ListNode* first = head, *prev = NULL, *second = head, *newhead = head;
    
    while (head && head->next) {
        /* initial first second */
        first = head;
        second = head->next;
        
        /* swap */
        first->next = second->next;
        second->next = first;
        if (prev)
            prev->next = second;
        else
            newhead = second; // set newhead (only one time)
        
        /* set a new head & prev for next step */
        prev = first;
        head = first->next;
    }
    return newhead;
}

해결 recursive

핵 간단하고 천재적인 풀이법. 항상 재귀는 정답을 리턴한다. first->next에는 그다음의 모든 노드들이 정렬을 마친 첫번째 노드를 가리키게하면 된다. first->next 에 swapPairs(second->next)를 저장하고. 재귀적으로 최종 모두정렬된 노드가 리턴된다. 재귀는 참 마법같다..

struct ListNode* swapPairs(struct ListNode* head){
    if (!head || !head->next)
        return head;
    struct ListNode* first = head, *second = head->next;
    
    first->next = swapPairs(second->next);
    second->next = first;
    
    return second;
}