Linked List | Swap Nodes in Pairs

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.)

2 노드씩 짝을 지어서, 순서를 바꾸라는 문제이다. 또한, 값을 변형하는것이 아닌, 노드의 위치를 바꾸라는 문제이다. 만약 노드의 갯수가 0개, 1개일 경우는 그대로 리턴해야하며, 노드 갯수가 홀수일 때, 마지막 노드는 그대로 둔다.

 

한번의 Trip만에 해결할 수 있는 방식이 떠올라 바로 코딩을 했다. 해법은 아래와 같다.

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode curr = head;
        ListNode temp = null;
        ListNode prev = dummy;
        while(curr != null && curr.next != null){
            temp = curr.next.next;
            curr.next.next = curr;
            prev.next = curr.next;
            curr.next = temp;
            prev = curr;
            curr = curr.next;
        }
        return dummy.next;
    }
}

* Time Complexity: O(N)

* Space Complexity: O(1)

 

0, 1개의 길이가 아니라면, 무조건 head가 변하기때문에 다양한 방법으로 풀 수 있겠지만, 맨 앞에 dummy node를 위치해서 그 다음값을 변형시키는 방식으로 풀었다. 또한, 여행을 하는 curr 포인터, curr의 다다음 노드를 임시 저장할 temp, 그리고 curr의 전에 있었던 노드를 기억하는 prev 포인터를 만들어서 진행했다. 먼저 curr의 다다음 노드를 기억하고, curr의 다음 노드의 next값을 현재 노드를 가르치도록 한다. 그 후, prev 노드의 다음값을 curr의 다음노드로 지정하고, curr의 next를 이전에 저장했던 temp (원래는 curr.next의 next 노드였다) 노드로 지정한다. 그 후, 다음 while loop을 위해 prev와 curr 값을 업데이트한 후 하나의 룹을 마무리한다. 만약 짝수길이의 리스트라면 curr가 null일때, 홀수라면 curr.next일때 while loop을 빠져나오게 된다.

 

이후, dummy의 다음 노드를 리턴해주면 되는데, 이렇게 하면, 0, 1일 뿐만 아니라 이미 head의 위치가 바뀌어있는 상황에서도 잘 적용이 된것을 볼 수 있다.

속도는 최상위권인 100%에 해당했고, 많은 포인터의 사용으로 중간정도에 위치한 Space 사용을 보였다.

 

자, 1번 2번 피카츄 위치 바꾸고, 3번 4번 피카츄 위치 바꿔서 새롭게 모여보자!