链表的中间节点

一天一道算法题

Posted by AndyCao on September 10, 2019

题目

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。

示例1

输入:[1,2,3,4,5]
输出:此列表中的结点 3

示例2

输入:[1,2,3,4,5,6]
输出:此列表中的结点 4

定义节点

class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
     }
 }

解法

func middleNode(_ head: ListNode?) -> ListNode? {
    // 快慢指针法
    var slow = head
    var fast = head
    while fast != nil && fast?.next != nil {
        fast = fast?.next?.next
        slow = slow?.next
        
    }
    return slow
}