Swap Nodes in Pairs(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]

Explanation:

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Output: [1]

Example 4:

Input: head = [1,2,3]

Output: [2,1,3]

 

Constraints:

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

일전에 한 번 풀었던 문제인데,

 

돌고 돌아 또 만났다.

 

한 번 풀어봅시다.

 

자고로 Linked List 문제는 Python, C, C++ 어떤 걸로도 풀 수 있어야 한다.

 

Container가 없기 때문에 C로 풀기 어렵다는 핑계가 없다!

 

1. Python

 

뭔가 Recursive하게 풀릴 거 같은데,, 잘 떠오르지가 않는다.

Naive하게 가보자.

 

아쓍 좀 오래 걸렸다-_- 간만에 머리가 좀 꼬였네.

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: ListNode) -> ListNode:
        if not head or not head.next : return head
        # Sentinel Node 이용..
        dummy = ListNode(999,head)
        prev = dummy
        curr = head
        while curr and curr.next :
            prev.next = curr.next # sentinel -> 2
            prev = curr # sentinel:1
            temp = curr.next.next
            curr.next.next = curr
            curr.next = temp
            curr = temp # curr -> 3
        return dummy.next

 

Recursive Pseudo code는 아래와 같다.

겁나 단순 그 잡채 ;;

        # # recursive
        # if not head or not head.next:
        #     return head

        # first_node, second_node = head, head.next

        # first_node.next = self.swapPairs(second_node.next)
        # second_node.next = first_node

        # return second_node

 

 

다시 Dummy를 이용해서 C로 풀어보자.

 

2. C

 

//  * Definition for singly-linked list.

  struct ListNode {
      int val;
      struct ListNode *next;
  };
 
struct ListNode* swapPairs(struct ListNode* head) {
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode* prev = dummy;
    struct ListNode* curr = head;
    
    while(curr && curr->next){
        prev -> next = curr->next;
        prev = curr;
        struct ListNode* temp = curr->next->next;
        curr->next->next = curr;
        curr->next = temp;
        curr = temp;
    }
    struct ListNode* ans = dummy->next;
    free(dummy);
    return ans;
}

 

 

3. C++

C++로는 Recursive하게 풀어보기!

첫 만남은 어렵긴 한데.. 진짜 아름답긴 하다 Recursive 함수..!

//   Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
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;
    }
};