Swap Nodes in Pairs

7283 ワード

# 전체 길이가 짝수개인 linked_list 가 주어지면 쌍으로 순서를 바꿔라

# 원본을 따로 저장해 놓은 것을 가지고 node 를 2칸씩 이동하면서 값을 바꿔줌

# 그리고 원본을 리턴

# copy 에 head 의 참조를 연결한 다음 값을 바꾸면 head 에도 반영됨

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

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

        copy = head

        while copy and copy.next:

            first_value = copy.val
            second_value = copy.next.val

            copy.val = second_value
            copy.next.val = first_value
            # copy = copy.next.next
            # copy = head.next.next
            copy = copy.next.next

        return head

# head 를 받아서 쌍으로 순서를 바꿔줘야 하는데
# head , 즉 원본을 조작을 하면은 이동하면서 하기 힘들어
# head 의 복사본을 따로 만들어 줘야함
# 그게 dummy

# ex> 1,2,3,4

# dummy = 0,1,2,3,4
# dummy 의 순서를 바꿔서 리턴을 할건데
# 연결리스트 특성상 접근할려면 다 순회해야 함
# 순회하는 데 사용할 current 복사본 생성
# current = 0,1,2,3,4

# 근데 1,2,3,4 에서 순서를 쌍으로 바꿔줘야 하기 때문에

# 0,1,2,3,4 에서 next , next next 가 있을 때만 반복

# 원재료 first 1,2,3,4
# 순서바꾸기 위한 저장소 second 2,3,4
# 1,2,3,4 에 2,3,4, 의 next 를 연결시킨다.
# 1,3,4
# second next 에 1,3,4 를 연결시킨다.
# 그러면 second 가 2,1,3,4 가 된다.
# 순서변경이 완료되었으므로
# current 에 연결시킨다.
# current 는 dummy 의 참조를 받고 있기 때문에 dummy 도 순서가 변경된다.

# 이후 current 는 다음 순서 변경을 위해서 두칸 이동한다.
# 두칸 이동한 dummy 의 참조를 받게 되고

# 이후 반복문에서 순서가 변경되면 두칸 이동한 dummy 에서 순서가 변경된다.

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

        dummy = ListNode(0, head)

        current = dummy

        while (current.next and current.next.next):

            first = current.next
            second = current.next.next

            first.next = second.next
            second.next = first

            current.next = second

            # current, dummy 0,2,1,3,4

            current = current.next.next
            # current = dummy.next.next

        return dummy.next