876. Middle of the Linked List

Description of the Problem

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.

Constraints:

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

Solution - Fast and Slow Pointers

Tags: LinkedList Fast-slow Pointer

Explanation

Slow pointer move to right by 1 and fast pointer move to right by 2 if possible.

At the end of loop, slow pointer must point to the middle node or previous node of the middle node

Here we assume the linkedlist use 0-based indexing (i.e. list[0] indicate first element of the list)

At the termination of the loop, there are only two possible case:

fast pointer point to last element of the linkedlist
fast pointer point to second last element of the linkedlist;

Suppose the loop ran k times. It implies that fast pointer mvoed to right by 2k and slow pointer moved to right by k.

In case 1, this is because the number of nodes in the linkedlist is odd number. The total number of nodes is 2k + 1. list[k] is the middle node because there are k elements in list[0..k] and in list[k+1..2k+1] elements¹.

In case 2, this is becuase the number of nodes in the linkedlist is even number. The total number of nodes is 2k + 2. list[0..k] and list[k+1..2k+2] contains half number of total elements.¹ Thus return slow.next;

¹ The sub-indexing is exclusive. For example A[i..j] does not include A[j]

Code (Java)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return fast.next == null? slow : slow.next;
    }
}

Complexity

Time complexity:

\( T(n) = O(n/2) \)
- There are only nearly n/2 iterations

Auxiliary Space:

\( S(n) = O(1) \)
- Use only constant number of variables

Futher Discussion

Tags: Rust

Alternative way to implements LinkedList in Rust and How to move a pointer in Rust

Althougt it is possible to implement LinkedList in Rust by Rc<RefCell<T>>, I do not know why leetcode refuse to use it. I would like to provide another implementation that supports fast and slow pointers approach. The key difficulty is moving pointer.

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, PartialEq)]
struct LinkedNode {
    val : i32,
    next : Option<Rc<RefCell<LinkedNode>>>,
}

impl LinkedNode {
    fn new(val : i32, next: Option<Rc<RefCell<LinkedNode>>>) -> Option<Rc<RefCell<LinkedNode>>>{
        Some(
            Rc::new(
                RefCell::new(
                    LinkedNode{
                        val, 
                        next
                    }
                )
            )
        )
    }
}

fn main() {

    let node_2 = LinkedNode::new(2, None);
    let node_1 = LinkedNode::new(1, node_2.clone() );

    let head = LinkedNode::new(0,  node_1);
    
    // Move pointer by flat_map
    let safe_fast_pointer = head.clone()
        .and_then(|n| {let n = n.borrow(); n.next.clone() })
        .and_then(|n| {let n = n.borrow(); n.next.clone() });
    
    assert_eq!(safe_fast_pointer, node_2);
    
}

For another way to use fast and slow pointers without re-implement the LinkedList, see: link from leetcode

Leetbook