反转链表

一、题目

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

示例: 输入: 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]); // 创建头节点
    head = currNode;
    
    for (let i = 1; i < arr.length; i++) {
        let node = new Node(arr[i]); // 创建新节点
        currNode.next = node; // 将单签节点链接到创建的节点
        currNode = node; // 当前节点指向新创建的节点
    }

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

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

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

反转链表：

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 (opens new window)