力扣刷题记录

题目分类 ：链表

时间 ：2020-09-11

---

题目一 ：逆转链表

反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路
新建一个头指针，指针指向null，可作为要求返回的链表的头指针
遍历输入的单链表，不断地把链表第一个元素删除，将其插入新链表的第一个位置
tips ：开始做这类题目之前要熟练地掌握链表的增删查改操作

错误提示 ：在JS中一半使用对象实现链表。由于Object是引用类型，要注意链表的数据备份。

//如题
let b = {val : 2, next : null}
let a = {val : 1, next : b};
let head = {next : a};
let newHead = {};
//此时若想将a从head链表中删除，插入newHead的链表中，需要将a备份
let c = a;
newHead.next = c;//head -> c
c.next = null; // c -> null
//完成该操作以后还要讲a从第一个链表中删除
head.next = a.next;
//此时运行将会发现，head并不指向b，而是指向null

出现以上问题的原因在于let c = a 时，由于对象是引用类型，复制时是将a的地址拷贝给c，此时根据c的地址修改c，使得c.next = null后，a.next 同时也被修改了。因此正确的备份方式应该是如下

let b = {val : 2, next : null}
let a = {val : 1, next : b};
let head = {next : a};
let newHead = {};
//此时若想将a从head链表中删除，插入newHead的链表中，需要将a备份
let c = {};
c.val = a.val;
newHead.next = c;//head -> c
c.next = null; // c -> null
//完成该操作以后还要讲a从第一个链表中删除
head.next = a.next;

解题代码

var reverseList = function (head) {
    let newhead = {next : null};
    let cur = head.next;
    while(cur){     
        let pre = {};
        pre.val = cur.val;
        cur = cur.next;
        pre.next = newhead.next;
        newhead.next = pre;
    }
    return newhead
};

---

题目二 ：第k个数

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
注意：本题相对原题稍作改动
示例：
输入： 1->2->3->4->5 和 k = 2
输出： 4

思路
利用栈先进后出的特殊结构，将节点一个推进栈中，在一个个出栈，可以很方便地求到导数第K个节点的数值
js数组的push( )和pop ( )方法可以很方便地实现栈结构

代码

var kthToLast = function (head, k) {
    let stack = [];
    let cur = head;
    let res;
    while (cur) {
        stack.push(cur.val);
        cur = cur.next
    }
    for (let i = 0; i < k; i++) {
        res = stack.pop();
    }
    return res
};

---

题目三 ： 第K个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

思路

和上面唯一的区别是一个求的是节点，一个求的是节点后的链表。。。

代码

var getKthFromEnd = function(head, k) {
    let stack = [];
    let cur = head;
    let res;
    while (cur) {
        stack.push(cur);
        cur = cur.next;
    }
    for (let i = 0; i < k; i++) {
        res = stack.pop();
    }
    return res
};