问题
工程化
leetcode
提交运行等待结果是一件很漫长的事情,而我们从编写代码到debug
成功期间可能会失败 N次,所以本地有一个方便我们运行测试的环境还是蛮重要的。
这里我选择建立了一个工程,将题解代码放在里面。
leetcode
题解调试过程中自定义的数据结构、方法有很多都是可以复用的,
所以,我们尽可能地复(tou)用(lan)。
节点类定义
1 | class ListNode(var `val`: Int) { |
吐槽,
val
与kotlin
的关键字冲突,所以要通过` `来转义(😢)。
ListNode?#reverse
kotlin 基操,给ListNode?
定义一个扩展方法reverse
,将具体的实现写在这里。
1 | // ListNode.kt |
单元测试
1 | // Solution206.kt |
这里用到了两个我自定义的扩展方法:
- List#toLinkedList,将
List
转换为单链表 - ListNode#toList,将单链表转换为
List
PS: 目前题解还不多,日后完善了可能会开源回馈社区
解法
双指针迭代法
要反转链表,核心就是将节点的next
指针指向前驱
但当前节点无法访问过去的节点(前驱)
因此需要保存前驱节点
申请两个指针:
prev
,最初指向NULL
;cur
,最初指向HEAD
- 不断遍历
cur
,每次迭代到cur
,将cur.next -> prev
(指针反指),然后prev
和cur
前进一格 cur
迭代完成(cur
为NULL
),prev
所在的就是最后一个节点
核心代码如下:
1 | while(cur != null){ |
reverse 实现
1 | fun ListNode?.reverse(): ListNode? { |
边界情况
kotlin
在语言层面支持空安全,结合IDE
的提醒,时刻提醒我们注意边界!
1 | // 如果当前链表为空或者只有一个节点,直接返回自身 |
递归解法
TODO