「算法修炼」 Leetcode - 链表

Keep coding , Keep learning .

一、基本概念

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

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

二、链表的类型

• 单链表

  单链表中的指针域只能指向节点的下一个节点。

• 双链表

  每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

  双链表 既可以向前查询也可以向后查询。

• 循环链表

  链表首尾相连

  循环链表可以用来解决约瑟夫环问题。

三、链表的声明

class ListNode {
  val;
  next = null;
  constructor(value) {
    this.val = value;
    this.next = null;
  }
}

四、性能分析

链表特性和数组特性对比

	插入/删除（时间复杂度）	查询（时间复杂度）	适用场景
数组	O(n)	O(1)	数据量固定，频繁查询，较少增删
链表	O(1)	O(n)	数据量不固定，频繁增删，较少查询

五、例题

链表操作的两种方式：

1. 直接使用原来的链表来进行操作。
2. 设置一个虚拟头结点在进行操作。

class ListNode {
  val;
  next = null ;
  constructor(value){
    this.val = value;
    this.next = null;
  }
}

1. 移除链表元素

leetcode - 203.移除链表元素

链表操作的两种方式：

• 直接使用原来的链表来进行删除操作。

  • 若是移除头节点 - 将头结点向后移动一位
  • 若是移除其它节点 - 通过前一个节点来移除当前节点

• 设置一个虚拟头结点在进行删除操作。

  • 设置虚拟头结点
  • 移除其它节点

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    // 定义虚拟头结点
    const newHead = new ListNode(0,head)
    // 移除其它节点
    let cur = newHead
    while(cur.next){
        // 是否存在下一节点
        if(cur.next.val === val){
            // 移除下一个节点
            cur.next =  cur.next.next
        } else {
            cur = cur.next
        }
    }
    return newHead.next
};

2. 设计链表

leetcode-707.设计链表

要实现链表的五个接口功能：

• 获取链表第index个节点的数值
• 在链表的最前面插入一个节点
• 在链表的最后面插入一个节点
• 在链表第index个节点前面插入一个节点
• 删除链表的第index个节点

class LinkNode {
    constructor(val, next) {
        this.val = val;
        this.next = next;
    }
}


class MyLinkedList {
    //单链表
    constructor(){
        // 存储节点数量
        this._size = 0
        // 存储头尾节点
        this._head = null
        this._tail = null
    }

    getNode(index){
       if(index < 0 || index >= this._size) return null;
        // 创建虚拟头节点
        let cur = new LinkNode(0, this._head);
        // 0 -> head
        while(index-- >= 0) {
            cur = cur.next;
        }
        return cur;
    }

    get(index){
        if(index < 0 || index >= this._size) return -1;
        // 获取当前节点
        return this.getNode(index).val;
    }

    addAtHead(val){
        const node = new LinkNode(val, this._head);
        this._head = node;
        this._size++;
        if(!this._tail) {
            this._tail = node;
        }
    }

    addAtTail(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;
    }

    addAtIndex(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++;
    }

    deleteAtIndex(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--;
    }
}

3. 反转链表

leetcode-206.反转链表

** 思路**：

1. 定义一个新的链表，实现链表元素的翻转，但这是对内存空间的浪费。

2. 改变原链表的next指针的指向，直接将链表反转。

   • 定义两个指针，cur指向当前节点，初始时为head；pre指向cur的前一节点，初始时为null
   • 反转过程就是一次变量赋值的交换，使原来的cur.next的指向pre，需要先使用temp保存一下cur.next，然后改变cur.next = pre，使其指向pre。
   • 继续移动指针cur，而cur的下一个位置就是上一次的cur.next，所以将temp保存的cur.next赋值给cur即可。
   • 最后，当cur 指针已经指向了null代表循环结束，链表反转完毕。

var reverseList = function(head) {
    if(!head || !head.next) return head;
    let temp = null
    let pre = null
    let cur = head
    while(cur){
        temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    }
    return pre
};

4. 两两交换链表中的节点

leetcode-24.两两交换链表中的节点

var swapPairs = function(head) {
  let ret = new ListNode(0, head)
  let temp = ret
  while (temp.next && temp.next.next) {
    let cur = temp.next.next
    pre = temp.next
    pre.next = cur.next
    cur.next = pre
    temp.next = cur
    temp = pre
  }
  return ret.next;
};