leetcode/python/ 876. Middle of the Linked List

 

Description

Middle of the Linked List - LeetCode

Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.

 

---

Process

Constraints:

• The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

 

연결된 노드의 중간 노드를 반환하는 문제다. 처음에는 순회하면서 이전의 연결을 하나씩 끊어줘야 하나? 했는데 어차피 주어진 ListNode는 singly로 구현되어 있다. 즉, 이전 노드의 정보를 애초에 가지고 있지 않다. 그렇다면 노드의 길이만 알면 그 중간 노드를 구할 수 있다. 

따라서 head 노드를 순회하면서 각 노드의 정보를 리스트에 저장하고, 그 리스트의 중간 요소를 반환하도록 구현했다.

 

---

Solution: Time: 19 ms (99.63%), Space: 13.8 MB (91.28%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        nodes = []
        while head:
            nodes.append(head)
            head = head.next
            
        return nodes[len(nodes)//2]

 

while문 안에서 순차적으로 head를 옮겨가면서 nodes 리스트에 저장해주고 마지막에 그 nodes 리스트의 중간 인덱스 값을 반환한다.

---

Conclusion

처음에 너무 간단해서 함정인가? 했는데 아니었다. 이번엔 차근차근 문제를 읽었고, 간단하게 접근할 수 있었다. easy 단계를 처음으로 easy하게 푼 것 같다. 화이팅!