Middle of the Linked List

🏠 ⬅️ ➡️

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
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    ! Solves the problem "Given the 'head' of a singly linked list, return the middle node of the linked list."
    implicit none

    type :: node_t
        integer :: val
        type(node_t), pointer :: next => null()
    end type

    type(node_t), target :: head
    type(node_t), pointer :: current => null(), mid => null()
    integer :: i

    ! Examples
    call add_node(head, 1)
    call add_node(head, 2)
    call add_node(head, 3)
    call add_node(head, 4)
    call add_node(head, 5)
    print "(A)", get_middle_node(head)%val
    call delete_all_nodes(head)

    call add_node(head, 1)
    call add_node(head, 2)
    call add_node(head, 3)
    call add_node(head, 4)
    call add_node(head, 5)
    call add_node(head, 6)
    print "(A)", get_middle_node(head)%val
    call delete_all_nodes(head)

contains

    subroutine add_node(head, val)
        ! Adds a new node with value `val` at the beginning of the linked list.
        type(node_t), target :: head
        integer, intent(in) :: val
        type(node_t), pointer :: new_node

        allocate(new_node)
        new_node%val = val
        new_node%next => head%next
        head%next => new_node
    end subroutine

    function get_middle_node(head) result(mid)
        ! Returns the middle node of the linked list. If there are two middle nodes, returns the second one.
        type(node_t), target :: head
        type(node_t), pointer :: current, mid

        current => head%next
        mid => head%next

        do while (associated(current))
            if (associated(current%next)) then
                current => current%next%next
            else
                exit
            end if
            mid => mid%next
        end do
    end function

    subroutine delete_all_nodes(head)
        ! Deletes all nodes from the linked list.
        type(node_t), target :: head
        type(node_t), pointer :: current, next

        current => head%next
        do while (associated(current))
            next => current%next
            deallocate(current)
            current => next
        end do
    end subroutine
end program
❌ Compiled
❌ Executed
❌ Correct 
module linked_list

type :: node
    integer :: val
    type(node), pointer :: next => null()
end type

interface
    function get_middle(head) result(middle)
        type(node), pointer, intent(in) :: head
        type(node), pointer :: middle
    end function
end interface

contains

function get_middle(head) result(middle)
    type(node), pointer, intent(in) :: head
    type(node), pointer :: current, middle

    ! Initialize current to head
    current => head

    ! Loop through the list until we reach the end
    do while (associated(current%next))
        ! If we have not found the middle node yet,
        ! move to the next node
        if (.not. associated(middle)) then
            middle => current
        else
            middle => middle%next
        end if
        current => current%next
    end do

    ! Return the middle node
    middle => middle%next
end function

end module

program test_linked_list
    use linked_list
    implicit none

    ! Create a linked list with 5 nodes
    type(node), pointer :: head, current
    allocate(head)
    head%val = 1
    current => head
    do i = 2, 5
        allocate(current%next)
        current%next%val = i
        current => current%next
    end do

    ! Print the middle node of the list
    write (*,*) "Middle node: ", get_middle(head)%val

    ! Create a linked list with 6 nodes
    deallocate(head)
    allocate(head)
    head%val = 1
    current => head
    do i = 2, 6
        allocate(current%next)
        current%next%val = i
        current => current%next
    end do

    ! Print the middle node of the list
    write (*,*) "Middle node: ", get_middle(head)%val

end program
🌐 Data from online sources 
from collections import Counter

def is_n_straight_hand(hand, group_size):
    counts = Counter(hand)

    for card in sorted(counts):
        if counts[card] > 0:
            for i in range(group_size - 1, -1, -1):
                if counts[card + i] < counts[card]:
                    return False
                counts[card + i] -= counts[card]

    return True

The algorithm uses a hashmap (Python's `Counter` class, or `Map` class in JavaScript) to count the occurrences of each card value in the hand. Then, it iterates through the card values in sorted order (using `sorted()` for Python and `sort()` for JavaScript). For each card value with positive count, it checks that it can form a group of consecutive cards of size `groupSize`. If any of these groups cannot be formed, it returns False, otherwise returns True. This approach takes advantage of the sorted order to ensure that the consecutive groups are formed in a optimal way.

\

🌐 Data from online sources 
#include <map>
#include <vector>
using namespace std;

bool isNStraightHand(vector<int>& hand, int groupSize) {
    map<int, int> counts;

    for (int card : hand) {
        counts[card]++;
    }

    for (auto it = counts.begin(); it != counts.end(); ++it) {
        if (it->second > 0) {
            for (int i = groupSize - 1; i >= 0; --i) {
                if (counts[it->first + i] < it->second) {
                    return false;
                }
                counts[it->first + i] -= it->second;
            }
        }
    }

    return true;
}

The algorithm uses a hashmap (Python's `Counter` class, or `Map` class in JavaScript) to count the occurrences of each card value in the hand. Then, it iterates through the card values in sorted order (using `sorted()` for Python and `sort()` for JavaScript). For each card value with positive count, it checks that it can form a group of consecutive cards of size `groupSize`. If any of these groups cannot be formed, it returns False, otherwise returns True. This approach takes advantage of the sorted order to ensure that the consecutive groups are formed in a optimal way.

\