[Leetcode]876. Middle of the Linked List

limelimejiwon·2022년 3월 12일

📄 Description

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.

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.

💡 Solutions

1. Using Two Pointers

# 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]:
        slow, fast=head, head
        while fast and fast.next:
        return slow

🔎 Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Runtime: 46 ms
Memory: 13.9 MB

How it works

  • shift the slow pointer by one
  • shift the fast pointer by two (going twice as fast as the slow pointer)

📌 the fast pointer will hit the end of the linked list the same time the slow pointer will reach the middle of the linked list

2. Using Recursion Method


Make your lives Extraordinary!

0개의 댓글