[LeetCode] 24. Swap Nodes in Pairs - 문제풀이

Description

인접한 두개의 노드끼리 swap하여 반환하는 문제입니다.

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

Solution 1. Iteration(반복)

public ListNode swapPairs(ListNode head) {

    ListNode dHead = new ListNode(0);
    dHead.next = head;
    ListNode cur = dHead;
    while(cur.next != null && cur.next.next != null){
        //swap
        ListNode temp = cur.next;
        cur.next = cur.next.next;
        temp.next = cur.next.next;
        cur.next.next = temp;
        cur = cur.next.next;
    }
    return dHead.next;

}

반복문을 사용해 풀어내는 방법입니다. 두개의 swap대상 노드 이전 포인터에서 다음 두 노드를 swap하여 처리한 후 다시 포인터를 2칸 이동해줍니다.

• 공간복잡도 : O(1)
• 시간복잡도 : O(N)

Solution 2. Recursion(재귀)

public ListNode swapPairs2(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode second = head.next;
    ListNode third = second.next;

    second.next = head;
    head.next = swapPairs2(third);

    return second;
}

재귀호출을 통한 방법입니다. 두번째 노드의 다음 노드에 head 를 붙이고(swap) 두번째로 넘어간 기존 head의 next에 재귀호출한 세번째 노드를 붙여 준뒤 새로운 head인 두번째노드를 반환해줍니다.

• 공간복잡도 : O(1)
• 시간복잡도 : O(N)

Reference

Swap Nodes in Pairs - LeetCode