文章 212
评论 0
浏览 119896
LinkedList - 876. Middle of the Linked List

LinkedList - 876. Middle of the Linked List

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

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

  • The number of nodes in the given list will be between 1 and 100.

思路:

就是求出链表的终点,非常简单的题目,使用快慢指针,快指针每次走一步,慢指针每次走两步,之所以写一下,是因为很多链表类的题目,都会首先求一下链表长度,再继续往下做。比如有一道题,让把一个有序列表,从中间断开,在合并起来,变成摇摆数组之类的题目。

代码:

go:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    slow , fast := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    
    return slow
}


标题:LinkedList - 876. Middle of the Linked List
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/12/31/1577779972378.html

Nothing just happens, it's all part of a plan.

取消