链表的中间节点

2019/07/13 leetcode 链表

链表的中间节点

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

 

示例 1:

输入:[1,2,3,4,5]

输出:此列表中的结点 3 (序列化形式:[3,4,5])

返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。

注意,我们返回了一个 ListNode 类型的对象 ans,这样:

ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2:

输入:[1,2,3,4,5,6]

输出:此列表中的结点 4 (序列化形式:[4,5,6])

由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。  

提示:

给定链表的结点数介于 1 和 100 之间。

长度取半

思路

获取链表长度l,获取(int)l/2的节点

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

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function middleNode($head) {
        $prev = $head;
        $size=0;
        while( $prev ){
            $size++;
            $prev=$prev->next;
        }
        
        $posi = (int)($size/2);
        while($posi--){
            $head=$head->next;
        }
        return $head;
    }
}

复杂度分析

时间复杂度:O(N),其中 N 是给定列表中的结点数目。

空间复杂度:O(1)。

快慢指针

思路和算法

当用慢指针 slow 遍历列表时,让另一个指针 fast 的速度是它的两倍。

当 fast 到达列表的末尾时,slow 必然位于中间。

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

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function middleNode($head) {      
        # 快慢指针
        $fast = $head;
        $slow = $head;
        while( $slow!=null && $fast->next!=null ){
            $slow = $slow->next;
            $fast = $fast->next->next;
        }
        return $slow;
    }
}

复杂度分析

时间复杂度:O(N),其中 N 是给定列表中的结点数目。

空间复杂度:O(1)。

Search

    Table of Contents