反转链表

一、题目

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

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

二、解题思路

创建链表：

// 节点定义
function Node(val) {
    this.val = val;
    this.next = null;
}

// 链表定义
function createNodeList(arr) {
    if (arr.length === 0) return null;

    let head = null;
    let currNode = new Node(arr[0]); // 创建头节点 （头部 1）
    head = currNode;
    
    for (let i = 1; i < arr.length; i++) {
        let node = new Node(arr[i]); // 创建新节点
        currNode.next = node; // 将单签节点链接到创建的节点 // 1(head/currNode) -> 2(newNode)
        currNode = node; // 当前节点指向新创建的节点  // 1(head) - > 2(currNode)
    }

    return head;
}
// 创建链表
let head = createNodeList([1,2,3,4]); // 1 -> 2 -> 3 -> 4 -> null

// 遍历链表
function traverseList(head) {
    while(head) {
        console.log(head.val);
        head = head.next;
    }
}

// 打印链表
traverseList(head)
console.log(head);

反转链表：

// 思路
// 1. 定义两个指针： pre 和 cur ；pre 在前 cur 在后。
// 2. 每次让 pre 的 next 指向 cur ，实现一次局部反转
// 3. 局部反转完成之后， pre 和 cur 同时往前移动一个位置
// 4. 循环上述过程，直至 pre 到达链表尾部

// 过程
// null(pre) 1(curr) -> 2 -> 3 -> 4 -> null
// null <- 1(pre) -> 2(curr) -> 3 -> 4 -> null
// null <- 1 <- 2(pre) <- 3(curr) <- 4 -> null
// null <- 1 <- 2 <- 3(pre) <- 4(curr) -> null
// null <- 1 <- 2 <- 3 <- 4(pre) -> null(curr)
var reverseList = function(head) {
    let pre = null;
    let curr = head;
    while (curr) {
        let tmpNext = curr.next; // 1.临时保存下一个节点指针（重点）
        curr.next = pre;         // 2.反转当前节点指向
        pre = curr;              // 3.pre指针右移
        curr = tmpNext;          // 4.curr指针右移
    }
    return pre;
};

let newHead = reverseList(head);
traverseList(newHead);
console.log(newHead);

• leetcode