엔지니어 게시판
LeetCode 솔루션 분류

[7/22] 86. Partition List

컨텐츠 정보

본문

Medium
3949529Add to ListShare

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

 

Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

 

Constraints:

  • The number of nodes in the list is in the range [0, 200].
  • -100 <= Node.val <= 100
  • -200 <= x <= 200
Accepted
366,386
Submissions
745,447
태그 ,

관련자료

댓글 1

학부유학생님의 댓글

  • 익명
  • 작성일
Runtime: 38 ms, faster than 90.25% of Python3 online submissions for Partition List.
Memory Usage: 13.9 MB, less than 31.57% of Python3 online submissions for Partition List.
# 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]:
        if not head or not head.next: return head
        sub_head = head
        sub_prev = dummy = ListNode(0, head)
        
        while sub_head and sub_head.val < x:
            sub_head = sub_head.next
            sub_prev = sub_prev.next
        
        curr = sub_head
        prev = sub_prev
        
        while curr:
            if curr.val < x:
                tmp_next = curr.next
                sub_prev.next = curr
                curr.next = sub_head
                sub_prev = sub_prev.next
                
                prev.next = tmp_next
                curr = tmp_next
            else:
                curr = curr.next
                prev = prev.next
        
        return dummy.next
            
        
        
전체 396 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 186 명
  • 오늘 방문자 2,714 명
  • 어제 방문자 5,332 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,047 명
알림 0