86. Partition List

86. Partition List

 

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
    	"""
        x 기준값보다, 
        작은 더미 노드 리스트, 큰 더미 노드 리스트를 만들어서
        이어주기
        """
    
        # 작은 값 리스트와 큰 값 리스트의 더미 노드 생성
        small_dummy = ListNode(0)
        large_dummy = ListNode(0)

        # 포인터 초기화
        small = small_dummy  # 작은 값 리스트의 끝
        large = large_dummy  # 큰 값 리스트의 끝

        # 리스트 순회
        while head:
            if head.val < x:  # 현재 값이 x보다 작으면 작은 리스트에 추가
                small.next = head
                small = small.next
            else:  # 현재 값이 x 이상이면 큰 리스트에 추가
                large.next = head
                large = large.next
            head = head.next  # 다음 노드로 이동

        # 큰 값 리스트의 끝을 None으로 설정
        large.next = None
        # 작은 값 리스트와 큰 값 리스트 연결
        small.next = large_dummy.next

        # 작은 값 리스트의 시작 반환
        return small_dummy.next

 

https://youtu.be/KT1iUciJr4g?si=CU8JmV0JoWBfrlXQ

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        """
        x 기준값보다, 
        작은 더미 노드 리스트, 큰 더미 노드 리스트를 만들어서
        이어주기
        """
        left, right = ListNode(), ListNode()
        ltail, rtail = left, right

        while head:
            if head.val < x:
                ltail.next = head
                ltail = ltail.next
            else:
                rtail.next = head
                rtail = rtail.next
            head = head.next
        
        ltail.next = right.next
        rtail.next = None        

        return left.next