LeetCode 143(Reorder List, Python)

1. 문제 링크

• https://leetcode.com/problems/reorder-list/

 

2. 문제 설명

• linked list의 head가 주어졌을 때, 해당 list를 아래처럼 표현할 수 있다.
  • L0 → L1 → ... → Ln-1 → Ln 
• 이 때, 아래의 형태가 되도록 list를 reorder해라. 
  • L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ... 
• 여기서 node의 value자체를 수정하는 것이 아니라, node의 연결관계를 바꿔야 한다. 
• 예시1)
  • head가 [1,2,3,4]로 1→2→3→4의 연결관계를 가지고 있다면, 
  • 1→4→2→3으로 변경할 수 있다. output = [1,4,2,3]
• 예시2)
  • head가 [1,2,3,4,5]로 1→2→3→4→5의 연결관계를 가지고 있다면,
  • 1→5→2→4→3으로 변경이 된다. output = [1,5,2,4,3]

3. 처음 풀이

• 결국 더 좋은 방법을 찾지 못해서, time limit에 걸린채로 마무리하고.. 다른 풀이를 참고하였다.
  • a,b,c 세개의 커서를 만들어주고, c는 가장 오른쪽으로 옮겨서 가장 끝의 노드로 위치시킨다음에,
  • a.next에 c를 붙이고, 그 next에 b를 붙이는 방식을 반복하였다.
  • [1,2,3,4,5]가 있을 때, 각 Iteration을 돌때마다 아래처럼 head의 연결관계가 변경이 된다.
    • [1,5,2,3,4] 
    • [1,5,2,4,3] 
  • 하지만 여기서 문제는,, iteration돌 때마다, 계속 while문으로 c를 맨 끝으로 이동시켜야 하고, 
  • node를 많이 가지고 있는 head에 대해서는 너무 비효율적이다. 12개 test중에 1개 통과를 못했는데,, 그것의 head는 아래처럼 생겼다. 아래는 time limit 걸린 로직

submission 통과 못할만 하다

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """

        if not head:
            return head 

        if not head.next:
            return head

        a,b,c= head,head.next,head

        c_distance =0

        while c.next:
            c = c.next
            c_distance += 1

        while b.next:

            a.next = c            
            c.next = b

            a=b
            b=b.next

            c_count = 0
            while c_count < c_distance-1:
                c = c.next
                c_count +=1
            
            c_distance = c_count-1 # reset c_distance 
        
            c.next = None

 

4. 다른 풀이

• 결국 다른 풀이를 참고하게 되었다. 3가지 step으로 나눠서 코드를 작성하는데, 이것 모두 linked list에서 배운 것들이다.
  • 그것들을 총집합시킨 문제..였다.
• step1) slow, fast를 통해 head의 중간 node를 찾는다. [1,2,3,4,5,6]이라면, slow node의 head가 4에 위치할 수 있도록
• step2) [1,2,3], [4,5,6] 두개로 분리하고, 두번째 list에 대해 거꾸로 뒤집는다. [1,2,3], [6,5,4]가 될 수 있도록
  • Revsered Linked List: https://codingbubu.tistory.com/99
• step3) 분리된 [1,2,3], [6,5,4] linked list에 대해 
  • 1→6→2→5→3→4가 되도록 연결관계를 짓는다.
• step1) find middle
  • slow, fast = head, head로 저장하고, 
    • slow는 한칸씩 next로 이동시키고
    • fast는 두칸씩 next에 이동시키다 보면 slow는 중간 지점으로 이동이 된다. 
• step2) reverse second half
  • 뒤집은 것은 아직도 약간 헷갈리는데 아래 그림을 보면 이해가 쉽다.
  • 결국 앞에 None을 하나 만들어서 None→1→2→3→4→5 가 5→4→3→2→1→None이 되도록 작업하는 것.

• step3) merge lis
  • 분리된 [1,2,3], [4,5,6]을 각각 head1, head2라고 하였을 때,
    • head1의 다음 노드를 nxt에 keep해두고,
    • head1의 다음노드를 head2로 설정하여, 연결리스트를 병합한 뒤,
    • head1를 head2로 이동을 시켜서, 다음 iteration에서 head1이 새로운 연결리스트의 끝을 가리키도록 한다.
    • 그리고 head2를 다음 노드로 이동시켜서, 다음 iteration에서 head2가 새로운 연결리스트의 끝을 가리키도록 한다. 
  • [1,2,3], [4,5,6]이 다음과 같이 반복이 되면,
    
    • 첫 iteration에서 head1: 1→6→2→3, head2: 5→4
    • 두번째 iteration에서 head1: 1→6→2→5→3, head2: 4
    • 마지막 iteration에서 head1: 1→6→2→5→3→4, head2: None이되고,
    • while문이 head2가 존재할 때까지만 반복하므로 iteration이 종료된다.

class Solution:
    def reorderList(self, head):
        if not head:
            return 

        #step 1: find middle            
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        #step 2: reverse second half
        prev, curr = None, slow.next

        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
    
        slow.next = None
        
        #step 3: merge lists
        head1, head2 = head, prev
        while head2:
            nxt = head1.next            
            head1.next = head2
            head1 = head2
            head2 = nxt

 

 

 

5. 배운 점

• linked list에서 가장 헷갈렸던 부분이 아래처럼 구현하는 부분이었는데
  • nxt = head1.next
  • head1.next = head2 
• nxt = head1.next는 그냥 'node'가 이동이 된다고 생각하고,
• head1.next = head2는 연결관계인 화살표가 바뀐다고 생각하니 편했다.
• 이번 문제에서도 [1,2,3], [4,5,6]에 대해서 아래처럼 위 아래로 두고, 위에 nxt, h1, h2의 위치를 옮기고, next를 쓰면 화살표를 이동하는 구조로 작성하니 좀 더 이해가 쉬워졌다. 
  • [1,2,3]
  • [4,5,6]