LeetCode 876. Middle of the Linked List

Problem:

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

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

 

Example 1:

Input: [1,2,3,4,5]

Output: Node 3 from this list (Serialization: [3,4,5]) The returned node has value 3. (The judge's serialization of this node is [3,4,5]). Note that we returned a ListNode object ans, such that: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

 

Example 2:

Input: [1,2,3,4,5,6]

Output: Node 4 from this list (Serialization: [4,5,6]) Since the list has two middle nodes with values 3 and 4, we return the second one.

 

-Summary-

1. Copy the original linked list.

2. Traverse the copied linked list and find the length.

3. Traverse the original linked list until it reaches out to the middle. (Calculated from the copied linked list)

 

Leetcode의 정답을 보니, fast and slow pointer로 additional space 없이 푼 방법이 있었다. 오늘도 배운다.

 

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]