Swap Nodes in Pairs[M,Linked List,Recursion]

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

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

 

Example 1:

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

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [1]
Output: [1]

 

Constraints:

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

1. C

Recursive하게 푸는 것이 정석인 문제다.

어렵다..

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* swapPairs(struct ListNode* head) {
    if(!head || !head->next) return head;    

    struct ListNode* first = head;
    struct ListNode* second = head->next;
    
    first->next = swapPairs(second->next);

    second->next = first;

    return second;
}

짜증이 난다. 이렇게 간단하다고??

 

코드를 대놓고 보면서 치면 논리가 참 간단해보이는데, 이게 솔직히 백지에서 시작하라고 하면 도저히 머릿속에서 자연스럽게 떠오르지가 않는다.

 

recursive를 쓰지 않고 푸는 법.

이것 또한 굉장히 복잡허다.

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* swapPairs(struct ListNode* head) {
    if(!head||!head->next) return head;

    struct ListNode* newhead = head->next;
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;

    while(curr&&curr->next){
        struct ListNode* nextp = curr->next->next;
        struct ListNode* second = curr->next;

        second->next = curr;
        curr->next = nextp;

        if(prev){
            prev->next = second;
        }
        prev = curr;
        curr = nextp;
    }
    return newhead; // 그냥 return head->next를 하면 값이 다르다..
}

 

2. C++

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next) return head;
        
        ListNode* first = head;
        ListNode* second = head->next;

        first->next = swapPairs(second->next);
        second->next = first;

        return second;
    }
};

 

3. Python

Recursive 안 쓰고 풀어보기

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next : return head

        ans = head.next
        prev = None
        curr = head

        while curr and curr.next:
            first = curr.next
            second = curr.next.next

            first.next = curr
            curr.next = second

            if prev:
                prev.next = first
            
            prev = curr
            curr = second
        return ans