反转链表

题目描述

给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。

数据范围：1≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

示例

示例1

输入：{1,2,3}
输出：{3,2,1}

示例2

输入：{}
输出：{}
说明：空链表则输出空

代码

代码1 暴力，先转数组，再转链表

1. 先遍历链表，将链表转换为数组
   1. 使用while循环，因为是翻转的链表，构造数组时，直接先翻转好，使用unshift
2. 再通过数组，构建翻转后的链表
   1. 边界判断，如果数组长度为0，直接返回null
   2. 不为0，开始for循环遍历数组，构建新链表

function ReverseList(pHead){
    
    // 1. 先转换为翻转好的数组
    let tempArr = []
    while(pHead){
        tempArr.unshift(pHead.val)
        pHead = pHead.next
    }
    
    let len = tempArr.length
    // 2. 如果数组长度为零，直接返回null
    if(len === 0 ) return null 
    
    // 3. 使用翻转好的数组开始构造链表
    let newHead = new ListNode(tempArr[0]) // 等待返回的新头结点
    let prevNode = newHead // 前一个节点，默认先是头节点
    
    // 从第二个节点开始遍历
    for(let i = 1; i < len; i++){
        let currentNode = new ListNode(tempArr[i])
        // 4. 如果是最后一个节点
        if(i === len - 1 ) {
            prevNode.next = currentNode
            currentNode.next = null
        }else {
            // 5. 如果不是最后一个节点
            prevNode.next = currentNode // 上一个节点的next指向把当前遍历的节点
            prevNode = prevNode.next
        }
    }
    return newHead
}

代码2 三个指针来回倒

使用三个指针

1. prev = null
2. current = Phead
3. next = null

使用while遍历，遍历时，遍历current

1. 先保存下一个节点 next = current.next
2. 然后把当前节点的next指向前一个节点（翻转链表的指向） current.next = prev
3. 把前一个节点prev指向当前的current，prev = current
4. 改变current，开始翻转下一个节点 current = next

function ReverseList(pHead){
    if(!pHead) return null
    
    let current = pHead
    let prev = null
    let next = null
    while(current){
        next = current.next
        current.next = prev
        prev = current
        
        current = next
    }   
    return prev
}

代码3 递归

• 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点
• 此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
• 同时让当前结点的 next 指针指向NULL ，从而实现从链表尾部开始的局部反转
• 当递归函数全部出栈后，链表反转完成。

function ReverseList(pHead){
    // 递归的出口，遍历到最后一个节点时，返回
    if(pHead === null || pHead.next === null){
        return pHead
    }
    
    // 每次递归都会保存当前的状态，比如{1,2,3}
    // 第一次 1
    // 第二次 2
    // 第三次 3
    // 遍历到3的时候，有返回值了，返回的就是最后一个节点
    let vHead = ReverseList(pHead.next)
    // 让当前节点下一个节点的next指向当前节点
    pHead.next.next = pHead
    // 同时让当前结点的 next 指针指向NULL ，从而实现从链表尾部开始的局部反转
    pHead.next = null
    
    return vHead
}

题目来源

JZ24 反转链表