代码随想录-链表

关于链表

什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义：

//Definition for singly-linked list.
function ListNode(val, next) {
	this.val = (val===undefined ? 0 : val)
 	this.next = (next===undefined ? null : next)
 }

203.移除链表元素

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    const newListNode = new ListNode(0, head)
    // 注意这里引用数据类型，头节点固定不变为手动添加的0，但赋给cur后，后面的节点会随着cur.next的更改而更改
    let cur = newListNode
    // 从第二个节点开始遍历（第一个节点是多添加的，最后要去掉）
    while(cur.next){
        // 下一个节点碰到指定数字，跳过
        if(cur.next.val === val){
            cur.next = cur.next.next
            continue
        }
        // 下一个节点不是指定数字，不用跳过，正常遍历
        cur = cur.next 
    }
    // 注意去除第一个节点
    return newListNode.next
};

707.设计链表

利用虚拟头节点，很方便

// 构造一个链表类,构造链表
class LinkNode {
    constructor(val, next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * Initialize your data structure here.
 * 单链表 储存头尾节点 和 节点数量
 */
var MyLinkedList = function() {
    this._size = 0;
    this._tail = null;
    this._head = null;
};

/**
 * Get the value of the index-th node in the linked list. If the index is invalid, return -1. 
 * 返回的是节点（包含内容与下标）
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.getNode = function(index) { 
    // index超过size或者小于0直接返回-1（没有）
    if(index < 0 || index >= this._size) 
        return null;
    // 创建虚拟头节点
    let cur = new LinkNode(0, this._head);
    // 0 -> head
    // 一直遍历链表，直到第index位
    while(index-- >= 0) {
        cur = cur.next;
    }
    return cur;
};
// 给下标，获取内容
MyLinkedList.prototype.get = function(index) {
    if(index < 0 || index >= this._size) 
        return -1;
    // 获取当前节点
    return this.getNode(index).val;
};

/**
 * Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. 
 * @param {number} val
 * @return {void}
 */
//  从头部增加链表节点
MyLinkedList.prototype.addAtHead = function(val) {
    // 先新建一个链表，val是头，this._head作为他的next
    const node = new LinkNode(val, this._head);
    this._head = node;
    // 记录大小的更改
    this._size++;
    if(!this._tail) {
        this._tail = node;
    }
};

/**
 * Append a node of value val to the last element of the linked list. 
 * @param {number} val
 * @return {void}
 */
//  从尾部新增链表节点
MyLinkedList.prototype.addAtTail = function(val) {
    // 新建一个链表
    const node = new LinkNode(val, null);
    this._size++;
    // 如果有尾巴，好说
    if(this._tail) {
        this._tail.next = node;
        this._tail = node;
        return;
    }
    // 如果没尾巴，更好说
    this._tail = node;
    this._head = node;
};

/**
 * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
    if(index > this._size) return;
    if(index <= 0) {
        this.addAtHead(val);
        return;
    }
    if(index === this._size) {
        this.addAtTail(val);
        return;
    }
    // 获取目标节点的上一个的节点
    const node = this.getNode(index - 1);
    node.next = new LinkNode(val, node.next);
    this._size++;
};

/**
 * Delete the index-th node in the linked list, if the index is valid. 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
    if(index < 0 || index >= this._size) return;
    if(index === 0) {
        this._head = this._head.next;
        // 如果删除的这个节点同时是尾节点，要处理尾节点
        if(index === this._size - 1){
            this._tail = this._head
        }
        this._size--;
        return;
    }
    // 获取目标节点的上一个的节点
    const node = this.getNode(index - 1);    
    node.next = node.next.next;
    // 处理尾节点
    if(index === this._size - 1) {
        this._tail = node;
    }
    this._size--;
};

// MyLinkedList.prototype.out = function() {
//     let cur = this._head;
//     const res = [];
//     while(cur) {
//         res.push(cur.val);
//         cur = cur.next;
//     }
// };
/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

206.反转链表

方法一：递归

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 递归法反转链表
var reverse = function(pre, head) {
    // 空链表直接返回
    if(!head) return pre;
    // 保存原链表的下一个元素
    const temp = head.next;
    // 反转
    head.next = pre;
    // pre往下挪一位
    pre = head
    // 递归
    return reverse(pre, temp);
}

var reverseList = function(head) {
    return reverse(null, head);
};

方法二：双指针

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
//  双指针法反转链表
var reverseList = function(head) {
    // 如果原链表为空或只有一个元素，直接返回
    if(!head || !head.next) {
        return head;
    }
    // temp用来保存链表元素 pre为反转之后的头节点
    // pr和ecur形成双指针
    let temp = null, pre = null, cur = head;
    while(cur) {
        temp = cur.next
        cur.next = pre
        // pre往下挪一位
        pre = cur
        // cxur往下挪一位
        cur = temp
    }
    // temp = cur = null;
    return pre;
};

24.两两交换节点内容

其实就是交换指针。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
    // ret是比原链表多一个头部的链表
    let ret = new ListNode(0, head), temp = ret;
    //如果有两个连续的数才能交换
    while (temp.next && temp.next.next) {
        //   分别指向两个要交换的节点
        let cur = temp.next.next, pre = temp.next;
        // 交换1
        pre.next = cur.next;
        // 保存
        cur.next = pre;
        // 交换2
        temp.next = cur;
        // 往下移
        temp = pre;
    }
    return ret.next;
};

19.删除链表的倒数第n个节点

双指针法。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    // 一次扫描找到倒数第n个节点
    // 在填充一个头部之后，采取双指针法
    // 一个快指针指向第n+1个节点，一个慢指针指向头部节点
    // 当快指针挪到最后一个 ,慢指针所指的就是倒数第n个
    let ret = new ListNode(0, head)
    let slow = fast = ret
    while(n > 0){
        fast = fast.next
        n --
    }
    while(fast.next != null){
        fast = fast.next
        slow = slow.next
    }
    // 跳过下一个数 相当于删除
    slow.next = slow.next.next
    // 返回ret.next
    return ret.next
};

面试题02.07. 链表相交

简单来说，就是求两个链表交点节点的指针。 这里要注意，交点不是数值相等，而是指针相等。

方法是先通过两个链表的长度差值找到相同的起始结点,然后双指针遍历

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    // 分别求出链表A和链表B的长度,并得到他们长度的差值n
    // 如果一个比较小,然后把长的那个(比如A)往后移n
    // 现在往后移之后的A和比较短的B长度相等,使用双指针即可
    let lengthA = lengthB = 0;
    let headACopy1 = headACopy2 = headA, headBCopy1 = headBCopy2 = headB
    while(headACopy1 != null){
        lengthA ++;
        headACopy1 = headACopy1.next
    }
    while(headBCopy1 != null){
        lengthB ++;
        headBCopy1 = headBCopy1.next
    }
    // 如果A长,则要把A往后挪
    if(lengthA > lengthB){
        let n = lengthA - lengthB
        while(n --){
            headACopy2 = headACopy2.next
        }
    }
    // B更长,把B往后挪
    if(lengthB > lengthA){
        let n = lengthB - lengthA
        while(n --){
            headBCopy2 = headBCopy2.next
        }
    }
    // 以上统一了开始节点之后的长度,现在开始双指针遍历
    while(headBCopy2 != null){
        // 注意是同一个节点,不是同一个值(不能用.val代替)
        if(headACopy2 === headBCopy2){
            return headBCopy2
        }
        headACopy2 = headACopy2.next
        headBCopy2 = headBCopy2.next
    }
    return null
};

142.环形链表Ⅱ

环形指针，非常绕

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 先判断是否是环形链表
var detectCycle = function(head) {
    // 1或2个节点，直接返回
    if(!head || !head.next) 
        {
            return null;
        }
    // 双指针遍历链表
    let slow =head.next, fast = head.next.next;
    // 慢指针一次走一个，快指针一次走两个，如果有环，必定会在环里相遇
    while(fast && fast.next && fast!== slow) {
        slow = slow.next;
        fast = fast.next.next; 
    }
    // 这说明没环，直接返回 
    if(!fast || !fast.next ) {
        return null;
    }
    // 这时，结束了上面的while循环后，slow和fast节点均在环内相遇
    // 慢指针走了x + y步
    // 快指针位于环内 ，走了x + y + n(y + z)步
    // 于是2(x + y) = x + y + n(y + z) ,即 x = n(y + z) - y
    // 即x = (n - 1) (y + z) + z
    // 当 n为1的时候，公式就化解为 x = z，
    // 这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
    // 让slow重新指向头部
    slow = head;
    
    // 快慢指针分别一个一个往后挪，会同时到达环形入口
    while (fast !== slow) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
};