8_17 연결리스트(페어의 노드 스왑)

문제: 연결리스트를 입력받아 페어 단위로 스왑하라.

1. 값만 교환

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        cur = head

        while cur and cur.next:
            # 값만 교환
            cur.val, cur.next.val = cur.next.val, cur.val
            cur = cur.next.next

        return head

간단하게 노드 구조는 그대로고 값만 변경하는 방법이다. 하지만 이 방법은 실용성이 떨어진다고 한다. 연결리스트들은 보통 복잡한 여러가지의 값들의 구조체로 되어 있고 거기서 값만 바꾸는 것은 어렵기 때문(?)이라고 한다... 흠 그런가

이 방법은 실용성은 떨어졌지만 이 문제에 한 해 시간도 매우 적게 걸렸다.

2. 반복 구조로 스왑

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        root = prev = ListNode(None)
        prev.next = head
        while head and head.next:
            # b가 a(head)를 가리키도록
            b = head.next
            head.next = b.next
            b.next = head

            # prev가 b를 가리키도록
            prev.next = b

            # 다음 번 비교를 위해 이동
            head = head.next
            prev = prev.next.next
        return root.next

아 위에서 왜 실용성이 떨어졌나 했는데 여기서 이유가 나왔다! 1-2-3-4-5-의 순서가 있을 때 3-4를 바꿀 때 연결된 2와5도 다 같이 변경해야 하기 때문이다. 당연한건데 왜 어렵지? 했던...;;

이 방법이 재미있는 것 같다. 처음에 b가 a를 가리키고 a는 b의 다음을 가리키도록 변경한다. 그리고 a의 전 노드 prev가 b를 가리키게하고 다음번 비교를 위해 2번 앞으로 간다. 그리고 문제 풀이에 맞게 while을 포함한다.

3. 재귀 구조로 스왑

재귀를 사용하면 더 깔끔하게 구할 수 있다!

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head and head.next:
            p = head.next
            # 스왑된 값 리턴 받음
            head.next = self.swapPairs(p.next)
            p.next = head
            return p
        return head

재귀를 이용하면 p변수는 하나만 있어도 되고 head를 바로 리턴할 수 있어 복잡도도 낮다.