FRTKL

876. Middle of the Linked List (Easy)

Problem

https://leetcode.com/problems/middle-of-the-linked-list/

  • 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.

Solution

Go

func middleNode(head *ListNode) *ListNode {
    l := 0
    tmp := head
    for tmp != nil {
        tmp = tmp.Next
        l++
    }
    for i := 0; i < l / 2; i++ {
        head = head.Next
    }
    return head
}

PHP

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function middleNode($head) {
        if (!$head->next) {
            return $head;
        }

        $ret = [];
        $depth = 1;
        while($head->next){
            $head = $head->next;
            $depth += 1;
            $ret[] = $head;
        }
        $ret[] = $head;
        return $ret[$depth/2-1];
    }
}

Impression

  • 今までの問題と違い、オブジェクトが絡んでくるとやや難しく感じた(しかしEasyの問題...)
Written By Fukuaki TAKANO
fortkle icon

Engineering Manager at Connehito inc.
Please contact me via twitter. @fortkle