如何求单链表的某个元素

1.已知链表，需要求链表某个位置的元素

其实这个问题解决思路很简单，遍历完查找就好了
编码比较简单就不做注释了

fun <T> printNode(node: Link1.Node<T>) {
        var temp = node
        println(temp.data)
        while (temp.next != null) {
            temp = temp.next!!
            println(temp.data)
        }

    }

2.再出个这个题的变形

如果是求这个链表倒数第k个元素，并且不允许遍历表该怎么做，这个就比较有意思了，其实可以做个类比，就比如说对数据操作做到时间和空间的最优解，那就是可以再去开辟一块内存，也就是用两个指针去解决，这两个指针的距离为k，那么快指针走到最后一个Node时，慢指针即为所求

//假设求倒数第2个元素
    fun <T> findSomeNode(node: Link1.Node<T>, count: Int): Link1.Node<T> {
        var slowNode = node
        var fastNode = node
        (0 until count).forEachIndexed { index, i ->
            fastNode = fastNode.next!!
        }

        while (true) {
            slowNode = slowNode.next!!
            if (fastNode.next == null) {
                return slowNode
            } else {
                fastNode = fastNode.next!!
            }
        }
    }

3.再来个变形

在不遍历整个表的情况下求出表的中间的Node，其实首先想到的还是遍历链表然后求某个位置的Node，但是如果还是加个前提，不让遍历链表，直接拿中间的Node呢，这次是不是想到了还是拿两个快慢指针去做，只要慢指针为1，快指针为2这样慢指针就是中间的Node，知道思路编码就容易了

//如果是偶数的话可能是两个
    fun <T> findMiddleNode(node: Link1.Node<T>): List<Link1.Node<T>> {
        var tempList = mutableListOf<Link1.Node<T>>()
        var slowNode = node
        var fastNode = node

        while (true) {
            if (fastNode.next == null) {
                //奇数，返回中间一个
                tempList.add(slowNode)
                return tempList
            }
            if (fastNode.next!!.next == null) {
                tempList.add(slowNode)
                tempList.add(slowNode.next!!)
                return tempList
            }

            slowNode = slowNode.next!!
            fastNode = fastNode.next!!.next!!
        }
    }

4.总结

经过和上文的对比应该能总结出这类问题的解决方法了，其实往深层理解就是时间和空间的转变就拿这个问题来说

1. 第一种解决方法是先遍历再去定位，那么首先要遍历完所有的，此时拿到长度再去定位到固定元素，拿极端举例子比方说倒数第一个，就需要遍历两遍数组
2. 第二种方法就是拿两个指针但是遍历一次就相当于用空间换了时间
   以上是个人理解，源码地址