문제

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

제한 사항

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

접근

인접한 노드 쌍을 짝지어 값을 swap하는 알고리즘 문제입니다. 값만 바꾸는 건 하지 말라네요 꼼수부리지 말라는거.

'이거 그냥 현재 노드랑 다음 노드 가져와서 바꿔주기만 하면 되는거 아닌가?' 하면서 접근했는데, 생각보다 신경써줘야할게 많더라구요 ㅠ

바꾸는 것까지야 좋은데 대상의 되는 노드의 부모와 다음 자식 노드에 대한 예외 처리까지 꼼꼼하게 해줘야 했습니다.

그래서 저 같은 경우엔 매개변수로 들어오는 노드를 답으로 제출하기 위해,

1. swap을 하고 매개변수head를 유지
2. 다음 쌍의 노드의 부모가 되는 노드를 따로 저장
3. swap하는 과정에서 부모와 다음 자식 노드에 대한 예외처리

하는 방식으로 접근했습니다. 조금 머리를 쓰긴 했지만 속도도 빠르게 나와 만족스러운 결과를 냈습니다.

답안

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(null == head)
            return null;

        if(null == head.next)
            return head;

        // Head 유지
        ListNode tmpNode = head;
        head = head.next;
        tmpNode.next = head.next;
        head.next = tmpNode;

        ListNode parentNode = tmpNode;
        tmpNode = tmpNode.next;
        while(null != tmpNode && null != tmpNode.next){
            ListNode node = tmpNode;
            ListNode nextNode = tmpNode.next;

            parentNode.next = nextNode;
            node.next = nextNode.next;
            nextNode.next = node;

            parentNode = node;
            tmpNode = node.next;
        }

        return head;
    }
}

여담

Leet Code에서 ListNode 관련 문제가 많아서 이참에 값을 추가하는 클래스도 따로 구현해봤어요.

앞으로 테스트할 때 디버깅도 할 수 있을거 같아 유용하게 쓰일거 같아요 ㅎㅎ.

Leet Code에서 디버깅을 하려면 따로 돈을 내야 하더라구요. 구매할 가치는 있다 생각하지만, 최대한 아껴서 필요할 때 사용하렵니다.

public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

     public void add(int val){
          if(null == next){
               next = new ListNode(val);
          }
          else{
               add(this, val);
          }
     }
     private void add(ListNode node, int val){
          if(null == node.next){
               node.next = new ListNode(val);
          }
          else{
               add(node.next, val);
          }
     }

     public void print(){
          ListNode node = this;
          while(null != node){
               System.out.print(node.val + " ");
               node = node.next;
          }
          System.out.println();
     }

}