876. Middle of the Linked List

Problem

Given the head of singly linked list, return the middle node of the linked list.

If there are two middel nodes, return the second middle node.

Example 1:

Input : head = [1,2,3,4,5]
Output : [3,4,5]
Explanation : The middle node of the list is node 3.

Example 2:

Input : head = [1,2,3,4,5,6]
Output : [4,5,6]
Explanation : Since the list has two middle nodes with values 3 and 4, we return the second one.

풀이

1. 입력과 출력이 처음보는 List Node이다.

• len(head)에서 오류가 발생해, head 자체를 print 해보면 아래와 같다.

  ListNode{val: 1, next:
     ListNode{val: 2, next:
        ListNode{val: 3, next:
           ListNode{val: 4, next:
              ListNode{val: 5, next: None}}}}}

2. 자료구조의 링크드리스트와 같이 head에서부터 시작해 링크(next)를 이용해 다음 노드로 순차적 이동을 해서 탐색할 수 있다.
3. 따라서,
   (1) 처음부터 끝까지 탐색해, 원소의 전체 개수를 파악하여 중앙 인덱스를 계산한다.
   (2) 다시 처음부터 탐색을 시작해 중앙 인덱스의 ListNode를 return 해주면 된다.

소스

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        length = 0
        tmp = head
        print(head)
        while True:
            length += 1
            if tmp.next == None :
                break
            tmp = tmp.next
        
        target = head
        for _ in range(length//2) :
            target = target.next
        return target

### 마치며

---

결과 Runtime : 38ms, faster than 5.84% of Python online submission for Middle of the Linked List.
=> 더 빨리 수행될 수 있는 방법을 찾아볼 것

---