Leetcode 24번 - Swap Nodes in Pairs

문제

연결 리스트가 주어집니다.

연결 리스트의 처음부터 노드를 2개씩 고르고, 두 노드를 바꾸어줍니다. 모든 노드를 교환한 후 연결리스트를 반환합니다.

 

단, 노드의 값을 바꾸는게 아니라 노드 자체를 바꿔줘야 합니다.

 

아래는 예시입니다.

 

---

살펴보기

아직 연결 리스트에 익숙하지 않아서 그림을 그려보면서 차근차근 풀어보았다.

 

우선 더미 노드를 만들고, 더미 노드의 다음 노드에 주어진 노드를 연결한다.

물론 더미 노드의 값은 아무거나 상관없다.

 

그리고 더미 노드를 가리키는 포인터를 만들어준다. 변수명은 curr로 설정했다.

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode curr = dummy;

 

curr의 다음 노드와, 다음 다음 노드를 가리키는 포인터를 하나씩 만들어준다.

변수명은 각각 first, second로 했다.

ListNode first = curr.next;
ListNode second = curr.next.next;

 

first의 다음 노드에 second의 다음 노드가 오도록 연결한다.

 

그러면 아마 다음 그림과 같은 모습이 될 것이다.

first.next = second.next;

 

 

second의 다음에 first가 오게 연결한다.

second.next = first;

 

이제 curr의 다음 노드에 second가 오게 한다.

 

curr.next = second;

 

위의 그림을 한 줄로 쭉 펴면 first와 second의 위치가 바뀐 것을 알 수 있다!

 

 

이제 curr를 두 칸 옆으로 옮기고, 옮긴 위치를 기준으로 다시 first와 second를 정하고 노드를 교환해주면 되겠다.

 

---

풀어보기

ListNode dummy = new ListNode(0,head);
ListNode curr = dummy;

while(curr.next != null && curr.next.next != null){
    ListNode first = curr.next;
    ListNode second = curr.next.next;
    first.next = second.next;
    second.next = first;
    curr.next = second;
    curr = curr.next.next;
}

return dummy.next;