给定一个单向链表,怎么找到该链表的中位节点?
可以使用快慢指针,定义 2 个指针变量,慢指针移动步数为 1,快指针移动步数为 2,当快指针移动到链表尾部时,慢指针就恰好指向中位节点了。
代码如下(kotlin编写):
/**
* 链表数据结构
*/
class Node constructor(val data: Char) {
var next: Node? = null
override fun toString(): String {
val sb = StringBuilder()
sb.append(data)
var tmp: Node? = next
while (tmp != null) {
sb.append(tmp.data)
tmp = tmp.next
}
return sb.toString()
}
}
//为了测试方便,将字符转换为链表来存储
fun toLinkedListStr(str: String?): Node? {
if (str.isNullOrEmpty())
return null
var head: Node? = null
var next: Node? = null
for (ch in str) {
val node = Node(ch)
next?.next = node
next = node
if (head == null) {
head = node
next = node
}
}
return head
}
fun findMiddleNode(head: Node?): Node? {
head ?: return null
head?.next ?: return head
var fast: Node? = head
var slow: Node? = head
while(fast?.next != null) {
fast = fast?.next?.next
slow = slow?.next
}
//此时 fast 指针如果不为空,则链表长度为奇数个,slow 指针刚好指向链表的正中间节点
//如果 fast 指针为空,则链表长度为偶数个,slow 指针指向的是链表长度一半的后一个节点
return slow
}
fun main() {
val str1 = toLinkedListStr("abcde")
println("$str1 的中位节点是:${findMiddleNode(str1)?.data}")
println(findMiddleNode(toLinkedListStr(""))?.data)
println(findMiddleNode(toLinkedListStr("a"))?.data)
println(findMiddleNode(toLinkedListStr("ab"))?.data)
println(findMiddleNode(toLinkedListStr("abc"))?.data)
}
执行结果为:
abcde 的中位节点是:c
null
a
b
b
时间复杂度:O(n)
空间复杂度:O(1)
网友评论