【LeetCode烹饪手册】206.反转链表

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思考

• 反转链表也就是把链表的指针反转
• 也就是把后面的节点的指向（原来为后面的后面）改为前面的节点
• 关键是怎么遍历节点

解法一、前后双指针法

• 后面节点的next指向前面的节点就行了

/**
 * @param {ListNode} head
 * @return {ListNode}
 */

// 双指针法
var reverseList = function(head) {
    let cur = null;
    let pre = head;
    while(pre !== null){
        let temp = pre.next;//temp代替pre移动
        pre.next = cur;//反转
        cur = pre;//cur 移动
        pre = temp;//pre正式移动
    }
    return cur;//最终cur是head
};

解法二、递归法

• 首先递归找到原链表结尾的ret，这个ret以后将会作为head节点
• 递归进去的肯定是（原链表head）的next
• 从ret递归返回到head，每一次都会执行反转，也就是把当前头节点的下一个节点的指向设置为这个头节点

//递归法
var reverseList = function(head){
    //设置找ret的递归出口
    if(head === null || head.next === null){
        return head;
    }
    //head.next就是每次递归的下一个
    let ret = reverseList(head.next);
    //head.next 就是下一个节点
    //head.next.next 就是下一个节点指向下一个节点的下一个节点的指针
    head.next.next = head;//反转
    head.next = null;
    return ret;
}

解法三、另一种双指针法

• 两个指针同时出发
• 反转：head节点的next节点的next指向cur
• cur移动
• head也移动，是之前保存的原链表head节点的next节点的next

//双指针法
var reverseList = function(head){
    if(head == null){
        return null;
    }
    //双指针相同开始位置
    let cur = head;
    while(head.next !== null){
        //保留head下一个节点的指向
        let temp = head.next.next;
        //head下一个节点指向cur，反转
        head.next.next = cur;
        //cur指向head下一个节点，cur移动
        cur = head.next;
        //head指向原来head下一个节点的指向
        //也就是说 head和cur指向一致
        head.next = temp;
    }
    return cur;
}

参考链接