876. Middle of the Linked List

---

Description

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

If there are two middle 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.
 

Constraints:

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

---

Code

// 876. Middle of the Linked List
type ListNode struct {
	Val  int
	Next *ListNode
}

func middleNode(head *ListNode) *ListNode {
	length := 0
	savedHead := head
	for savedHead != nil {
		length++
		savedHead = savedHead.Next
	}

	length /= 2

	for length != 0 {
		head = head.Next
		length--
	}

	return head
}

 

이 코드는 연결 리스트의 중간 노드를 찾는 함수를 구현합니다. 주어진 연결 리스트는 헤드 노드 head로 시작합니다.

먼저 코드는 주어진 연결 리스트의 길이를 구합니다. 이를 위해 반복문을 사용하여 연결 리스트의 모든 노드를 순회하고 길이를 계산합니다.

그런 다음, 연결 리스트의 길이를 절반으로 나눕니다. 이후에는 길이가 절반인 지점까지 포인터를 이동하여 중간 노드를 찾습니다.

이 코드의 시간 복잡도는 O(n)입니다. 연결 리스트의 길이를 계산하는 반복문은 연결 리스트의 모든 노드를 한 번씩만 방문하므로 O(n)의 시간이 소요됩니다. 그리고 중간 노드를 찾기 위해 다시 한 번 반복문을 사용하므로 전체적인 시간 복잡도는 O(n)입니다.

 

---

 

func middleNode(head *ListNode) *ListNode {
	middle, end := head, head

	for end != nil && end.Next != nil {
		middle = middle.Next
		end = end.Next.Next
	}

	return middle
}

 

하나의 포인터는 한 번에 한 노드씩 전진하고, 다른 포인터는 한 번에 두 노드씩 전진합니다. 따라서 두 번째 포인터가 연결 리스트의 끝에 도달할 때 첫 번째 포인터는 중간에 위치하게 됩니다.

이 알고리즘은 두 포인터가 각각 연결 리스트를 한 번씩만 순회하므로 전체적인 시간 복잡도는 O(n/2)이며, 상수를 무시하면 O(n)입니다. 따라서 이 코드는 선형 시간에 중간 노드를 찾습니다.