[파이썬 알고리즘] 16. 페어의 노드 스왑

1. 문제

leetcode 24. swap nodes in pairs
한방향 연결리스트가 주어지면 인접한 모든 두 노드의 방향을 바꾸어 바뀐 리스트의 head를 리턴하여라.

2. 반복을 이용한 풀이

  이 문제를 해결하기 위해서는 인접한 두 노드 간의 포인터 방향만 바꾸면 안된다. 앞에 있던 노드가 가리키는 포인터 방향도 바꾸어야한다. 포인터 세개를 관리하면서 반복문을 통해 문제를 해결할 수 있다.
먼저 head 뒤 노드를 b, 앞 노드를 prev라고 지정한다. 그리고 b가 head를 가리키고, head는 b 다음의 노드를 가리키도록 한다. 원래 head를 가리키던 prev는 p를 가리키도록 한다. 마지막으로 다음 비교를 위해 head, prev를 뒤로 한칸씩 옮긴다. 이 과정을 두 개 이상의 노드가 남아 있을 동안 반복한다.

3. 재귀를 이용한 풀이

주어진 노드 중 가장 앞 노드를 리턴하는 재귀함수를 이용해서 문제를 풀 수도 있다. 먼저 남은 노드가 1개 이하라면, 마지막 노드 또는 None일 head를 리턴한다. 남은 노드가 2개 이상이라면 head의 다음 노드를 p로 지정한다. 그리고 head가 가리킬 다음 노드를 재귀 호출을 통해서 지정한다. 전달되는 인자 head는 p 다음 노드를 넘겨준다. 그리고 p가 head를 가리키도록 화살표의 방향을 변경한다. 마지막으로 지금 맨 앞에 있는 노드인 p를 리턴한다. 리스트가 끝날 때까지 함수가 재귀적으로 호출되고, 리스트가 종료된다면 함수가 순차적으로 리턴되면서 바뀐 위치에 맞도록 연결이 이루어질 것이다.