LinkedList : Swap Nodes in Pairs

https://leetcode.com/problems/swap-nodes-in-pairs/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

reverse nodes in k-group의 이전 단계 문제같다.

아마 FAANG 면접관이라면 이 문제를 먼저 내고 follow up 문제로 reverse nodes in k group을 냈을거같다.

 

마침 어제 푼 문제라서 똑같이 풀었다.

# 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: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)

        groupBefore = dummy
        while True:
            groupEnd = self.findSecond(groupBefore)

            if not groupEnd:
                break

            groupAfter = groupEnd.next
            prev = groupEnd.next
            cur = groupBefore.next
            while cur != groupAfter:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp

            groupStart = groupBefore.next
            groupBefore.next = groupEnd
            groupBefore = groupStart

        return dummy.next

    def findSecond(self, node):
        for i in range(2):
            if not node:
                break
            node = node.next
        return node

시간 복잡도 O(N)

공간 복잡도 O(1)

 

좀더 specialize 시켜봤다.

만약 면접에 나왔으면 난 이렇게 풀었을듯 하다.

# 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: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)

        before = dummy
        while True:
            if not before.next or not before.next.next:
                break

            left = before.next
            right = left.next
            after = right.next

            before.next = right
            right.next = left
            left.next = after

            before = left

        return dummy.next