링크드 리스트(리스트 중간지점 찾기)

리스트의 끝까지 가면서 카운트를 알아낸 뒤, 중간까지 순회하는 방법이 있다. 

 

 

위의 방법은 2path iteration이다. 길이를 알기위해 1번 답을 구하기 위해 1번 iterate했기 때문이다.

 

1path iteration으로 풀려면 아래와 같은 방법이 있다.

array를 사용한다. 리스트를 array에 담으면 자동으로 length를 알게되고 미들인덱스 value를 리턴하면 된다.

time complexity, space complexity는 O(n)이다. 

 

 

1path iteration에 space complexity를 O(1)로 줄이는 방법도 있다.

 

fast & slow pointer 방법이다. fast pointer는 2칸씩 움직이고 slow pointer는 1칸씩 움직인다.

 

 

# Title : Linked List의 중간 node를 찾기
# Chapter : Linked List

# 문제 : 주어진 LinkedList의 중간 node를 찾아서 return하여라
# 예제1 : 1→3→5→7→9
# output : 5→7→9

# 예제2 : 1→2→3→4
# output : 3→4

from typing import List

class ListNode:
  def __init__(self, x):
    self.val = x
    self.next = None

def createList(in_list:List[int]) -> ListNode:
  if len(in_list) == 0:
    raise RuntimeError("in_list must have data")        
  head_node = ListNode(in_list[0])
  last_node = head_node
  for idx in range(1,len(in_list)):
    node = ListNode(in_list[idx])
    last_node.next = node
    last_node = node
  return head_node

def printNodes(node:ListNode):
  crnt_node = node
  while crnt_node is not None:
    print(crnt_node.val, end=' ')
    crnt_node = crnt_node.next
  print()


class MiddleNode:
    def indexWay(self, head:ListNode) -> ListNode:
        total_count = 0
        crnt_node = head
        while crnt_node:
            crnt_node = crnt_node.next
            total_count += 1
        
        half_count = total_count // 2

        crnt_node = head
        for idx in range(half_count):
            crnt_node = crnt_node.next

        return crnt_node

    def arrayWay(self, head:ListNode) -> ListNode:
        node_array = []
        crnt_node = head
        while crnt_node:
            node_array.append(crnt_node)
            crnt_node = crnt_node.next
        return node_array[len(node_array) // 2]

    def fastSlow(self, head:ListNode) -> ListNode:
        slow_node = head
        fast_node = head

        while fast_node:
            if fast_node.next:
                slow_node = slow_node.next
                fast_node = fast_node.next.next
            else:
                break

        return slow_node


#index way
list_in = createList([1,3,5,7,9])
middle_node = MiddleNode()
middle_node = middle_node.indexWay(list_in)
printNodes(middle_node)

#array way
list_in = createList([1,3,5,7,9])
middle_node = MiddleNode()
middle_node = middle_node.arrayWay(list_in)
printNodes(middle_node)

#fast slow way
list_in = createList([1,3,5,7,9])
middle_node = MiddleNode()
middle_node = middle_node.fastSlow(list_in)
printNodes(middle_node)

 

참조 : (2) 코딩테스트, 초급, 리스트 중간지점 찾기 - YouTube