/*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!
}