/*class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param head ListNode类
* @return ListNode类
*/
export function ReverseList(head: ListNode): ListNode {
// 解法一:三指针法
// 用到一个 while 循环,所以时间复杂度为 O(n)
// 空链表则输出空
if (!head) return null
// 定义三个指针
let preNode: ListNode | null = null
let curNode: ListNode | null = null
let nextNode: ListNode | null = head
while (nextNode) {
// 第一个元素,删掉 next, 防止循环引用
if (!preNode && curNode) {
delete curNode.next
}
// 反转指针
if (preNode && curNode) {
curNode.next = preNode
}
// 整体向后移动指针
preNode = curNode
curNode = nextNode
nextNode = nextNode?.next
}
// 处理最后一个
curNode!.next = preNode
return curNode!
}