2w字 | 28道 LeetCode 题目带你看看链表的那些套路

整理了一下LeetCode上关于链表的热门题目，如有问题，欢迎指正！

相关文章：

【1】3.5w字 | 47道 LeetCode 题目带你看看二叉树的那些套路（上）

【2】3.5w字 | 47道 LeetCode 题目带你看看二叉树的那些套路（下）

1. 链表的概念

（1）链表的结构

在计算机里，不保存在连续存储空间中，而每一个元素里都保存了到下一个元素的地址的数据结构，我们称之为链表（Linked List）。链表上的每一个元素又可以称它为节点（Node），而链表中第一个元素，称它为头节点（Head Node），最后一个元素称它为尾节点（Tail Node）。

链表的结构定义中，包含了两个信息，一个是数据信息，用来存储数据的，也叫做数据域；另外一个是地址信息，用来存储下一个节点地址的，也叫做指针域。

可以看到，链表节点以整型作为数据域的类型，其中第一个链表节点，存储了 763 这个数据，指针域中呢，存储了一个 0x56432 地址，这个地址而 0x56432 正是第二个链表节点的地址。这样，第一个节点指向第二个节点，因此这两个节点之间，在逻辑上构成了一个指向关系。

在第二个节点的指针域中呢，存储了一个地址，是 0x0，这个地址值所对应就是 0。这是一个特殊的地址，我们称它为空地址，用 NULL 表示这个空地址。第二个链表节点指向空地址，就意味着它就是这个链表结构的最后一个节点。

在JavaScript中，链表的定义中包含两个属性，val 用来保存节点上的数据，next用来保存指向下一个节点的链接。使用一个构造函数来创建节点，在构造函数设置了这两个属性的值：

function ListNode(val) {
     this.val = val;
     this.next = null;
 }

注意，链表结构的指针域只有一个 next 变量，这说明每一个链表节点，只能唯一地指向后续的一个节点。在JavaScript中是没有指针的概念的，所以我们可以理解这个指针是一个地址的引用。

（2）链表与数组对比

其实，链表结构和数组结构很类似，只不过数组结构在内存中存储是连续的，链表结构由于有指针域的存在，它的每一个节点在内存中存储的位置未必连续。下面来对比一下两者的性能。

1）空间利用率 数组在创建之后大小是无法改变的，想要增加元素的话就必须重新创建一个新的数组。所，以有时为了能够动态地增加元素，在开始创建数组时会声明一个比需要的大小还多的空间出来，以便后面添加新的元素。这个时候就会造成空间上的浪费，所以，数组的空间利用率相当于本来需要的大小除以创建出来数组的大小。

而因为链表中的元素只有当需要的时候才会被创建出来，所以不存在需要多预留空间的情况。对于我们来说，只有节点里的值是可以利用上的，而保存节点地址的内存其实对于我们来说是无法应用的。所以链表的空间利用率上相当于值的大小除以值的大小和节点地址大小的和。

2）时间复杂度 访问数组元素的时间复杂度是 O(1)。而因为链表顺序访问的这个特性，访问链表中第 N 个元素需要从第一个元素一直遍历到第 N 个元素，所以平均下来的时间复杂度是 O(N)。

对于数组来说，插入操作无论是发生在数组结尾还是发生在数组的中间，因为都需要重新创建一个新的数组出来，并复制一遍之前的元素到新的数组中，所以平均的时间复杂度都是 O(N)。而对于链表来说，要是一直都能维护一个尾节点的地址的话，那么插入一个新的元素只需要 O(1) 的时间复杂度。而当插入一个元素到链表中间的时候，因为链表顺序访问的这个特性，需要先遍历一遍链表，从第一个节点开始直到第 N 个位置，然后再进行插入，所以平均下来的时间复杂度是 O(N)。

（3）链表的形式

1）单向链表 所有的链表节点中都只保存了指向下一个节点地址的信息。这种在一个节点中既保存了数据，也保存了指向下一个节点地址信息的链表，称之为单向链表（Singly Linked List）。如下图所示：

2）双向链表 单向链表有着只能朝着一个方向遍历的局限性，既然可以保存指向下一个节点地址的信息，也可以保存指向上一个节点地址的信息。这种在一个节点中保存了数据也保存了连向下一个和上一个节点地址信息的链表，称之为双向链表（Doubly Linked List）。和链表中尾节点的下一个节点只保存空地址一样，链表中头节点的上一个节点地址也保存着空地址，如下图所示：

（3）循环链表 无论是单向链表或者是双向链表，当遍历至尾节点之后就无法再遍历下去了，如果将尾节点指向下一个节点地址的信息更新成指向头节点的话，这样整个链表就形成了一个环，这种链表称之为循环链表（Circular Linked List）。如下图所示：

2. 链表的操作

在实现链表时候，通常在链表前面加一个假头，所谓假头，通常也叫作 Dummy Head 或者“哑头”。实际上，就是在链表前面，加上一个额外的结点。此时，存放了 N 个数据的带假头的链表，算上假头一共有 N+1 个结点。

那额外的结点不会存放有意义的数据。那么它的作用是什么呢？

其实，添加假头后，可以省略掉很多空指针的判断，链表的各种操作会变得更加简洁。关于链表的各种操作，主要是以下 6 种基本操作：

• 链表初始化
• 尾部追加结点
• 头部插入结点
• 查找结点
• 插入指定位置之前
• 删除结点

下面以 LeetCode 的707题《设计链表》为例，来实现一下单链表，题目要求将这 6 种基本的操作加以实现：注释中的 /code here/ 部分是填写相应的 6 种功能代码：

var MyLinkedList = function() {
   /* code here: 初始化链表 */
};

MyLinkedList.prototype.addAtTail = function(val) {
  /* code here: 将值为 val 的结点追加到链表尾部 */
};

MyLinkedList.prototype.addAtHead = function(val) {
  /* code here: 插入值val的新结点，使它成为链表的第一个结点 */
};

MyLinkedList.prototype.get = function(index) {
	/* code here: 获取链表中第index个结点的值。如果索引无效，则返回-1 */
  // index从0开始。
};
  
MyLinkedList.prototype.addAtIndex = function(index, val) {
	// code here:
  // 在链表中的第 index 个结点之前添加值为 val  的结点。
  // 1. 如果 index 等于链表的长度，则该结点将附加到链表的末尾。
  // 2. 如果 index 大于链表长度，则不会插入结点。
  // 3. 如果 index 小于0，则在头节点前插入
};

MyLinkedList.prototype.deleteAtIndex = function(index) {
	/* code here: 如果索引index有效，则删除链表中的第index个结点 */
};

（1）链表初始化

初始化假头链表，首先需要 new 出一个链表结点，并且让链表的 dummy 和 tail 指针都指向它，代码如下：

var listNode = function(val) {
    this.val = val
    this.next = null
};

var MyLinkedList = function() {
    this.dummy = new listNode()
    this.tail = this.dummy
    this.length = 0
};

初始化完成后，链表已经有了一个结点，但是此时，整个链表中还没有任何数据。因此，对于一个空链表，就是指已经初始化好的带假头链表。

虽然 head 和 tail 初始化完成之后，都指向null。但是这两者有一个特点，叫“动静结合”：

• 静：head 指针初始化好以后，永远都是静止的，再也不会动了。
• 动：tail 指针在链表发生变动的时候，就需要移动调整。

（2）尾部追加结点

尾部添加新结点操作只有两步，代码如下：

MyLinkedList.prototype.addAtTail = function(val) {
    // 尾部添加一个新结点
    this.tail.next = new listNode(val)
    // 移动tail指针
    this.tail = this.tail.next;
    // 链表长度+1
    this.length ++
};

带假头的链表初始化之后，可以保证 tail 指针永远非空，因此，也就可以直接去修改 tail.next 指针，省略掉了关于 tail 指针是否为空的判断。

（3）头部插入结点

需要插入的新结点为 p，插入之后，新结点 p 会成为第一个有意义的数据结点。通过以下 3 步可以完成头部插入：

• 新结点 p.next 指向 dummy.next；
• dummy.next 指向 p；
• 如果原来的 tail 指向 dummy，那么将 tail 指向 p。

对应的代码如下：

MyLinkedList.prototype.addAtHead = function(val) {
    // 生成一个结点，存放的值为val
    const p = new listNode(val)
    // 将p.next指向第一个结点
    p.next = this.dummy.next;
    // dummy.next指向新结点，使之变成第一个结点
    this.dummy.next = p;
    // 注意动静结合原则，添加结点时，注意修改tail指针。
    if (this.tail == this.dummy) {
      this.tail = p;
    }
    // 链表长度+1
    this.length ++
};

这段代码有趣的地方在于，当链表为空的时候，它依然是可以工作的。因为虽然链表是空的，但是由于有 dummy 结点的存在，代码并不会遇到空指针。

注意： 如果链表添加了结点，或者删除了结点，一定要记得修改 tail 指针。如果忘了修改，那么就不能正确地获取链表的尾指针，从而错误地访问链表中的数据。

（4）查找结点

在查找索引值为 index（假设 index 从 0 开始）的结点时，你需要注意，大多数情况下，返回指定结点前面的一个结点 prev 更加有用。好处有以下两个方面：

• 通过 prev.next 就可以访问到想要找到的结点，如果没有找到，那么 prev.next 为 null；
• 通过 prev 可以方便完成后续操作，比如在 target 前面 insert 一个新结点，或者将 target 结点从链表中移出去。

因此，如果要实现 get 函数，应该先实现一个 getPrevNode 函数：

MyLinkedList.prototype.getPreNode = function(index) {
    if (index < 0 || index >= this.length) {
      return -1;
    }
    // 初始化front与back，分别一前一后
    let front = this.dummy.next
    let back = this.dummy
    // 在查找的时候，front与back总是一起走
    for (let i = 0; i < index && front != null; i++) {
      back = front;
      front = front.next;
    }
    // 把back做为prev并且返回
    return back
};

有了假头的帮助，这段查找代码就非常健壮了，可以处理以下 2 种情况：

• 如果 target 在链表中不存在，此时 prev 返回链表的最后一个结点；
• 如果为空链表（空链表指只有一个假头的链表），此时 prev 指向 dummy。也就是说，返回的 prev 指针总是有效的。

借助 getPrevNode 函数来实现 get 函数：

MyLinkedList.prototype.get = function(index) {
    // 获取链表中第 index 个结点的值。如果索引无效，则返回-1。
    // index从0开始
    if (index < 0 || index >= this.length) {
      return -1;
    }
    // 因为getPrevNode总是返回有效的结点，所以可以直接取值。
    return this.getPreNode(index).next.val
};

（5）插入指定位置之前

插入指定位置的前面，有 4 个需求。

• 如果 index 大于链表长度，则不会插入结点。
• 如果 index 等于链表的长度，则该结点将附加到链表的末尾。
• 如果 index 小于 0，则在头部插入结点。
• 否则在指定位置前面插入结点。

其中，Case 1~3 较容易处理。可以直接写。重点在于 Case 4。现在已经有了 getPrevNode() 函数，就可以比较容易地写出 Case 4 的代码，思路如下：

• 使用 getPrevNode() 函数拿到 index 之前的结点 pre；
• 在 pre 的后面添加一个新结点。

以下是具体的 Case 1~4 的操作过程：

MyLinkedList.prototype.addAtIndex = function(index, val) {
  if (index > this.length) {
    // Case 1.如果 index 大于链表长度，则不会插入结点。
    return;
  } else if (index == this.length) {
    // Case 2.如果 index 等于链表的长度，则该结点将附加到链表的末尾。
    this.addAtTail(val);
  } else if (index <= 0) {
    // Case 3. 如果index小于0，则在头部插入结点。
    this.addAtHead(val);
  } else {
    // Case 4.
    // 得到index之前的结点pre
    const pre = this.getPreNode(index);
    // 在pre的后面添加新结点
    const p = new listNode(val);
    p.next = pre.next;
    pre.next = p;
    // 链表长度+1
    this.length++;
  }
};

（6）删除节点

删除结点操作是给定要删除的下标 index（下标从 0 开始），删除的情况分 2 种：

• 如果 index 无效，那么什么也不做；
• 如果 index 有效，那么将这个结点删除。

上面这 2 种情况中，Case 1 比较容易处理，相对要麻烦一些的是 Case 2。要删除 index 结点，最好是能找到它前面的结点。有了前面的结点，再删除后面的结点就容易多了。不过已经有了 getPrevNode 函数，所以操作起来还是很简单的。

以下是具体的操作过程

MyLinkedList.prototype.deleteAtIndex = function(index) {
  // Case 1. 如果index无效，那么什么也不做。
  if (index < 0 || index >= this.length) {
    return;
  }
  // Case 2. 删除index结点
  // step 1. 找到index前面的结点
  const pre = this.getPreNode(index);
  // step 2. 如果要删除的是最后一个结点，那么需要更改tail指针
  if (this.tail == pre.next) {
    this.tail = pre;
  }
  // step. 3 进行删除操作。并修改链表长度。
  pre.next = pre.next.next;
  this.length--;
};

（7）总结

使用哑结点来实现链表的总代码如下：

        /**
* Initialize your data structure here.
*/
var listNode = function(val) {
    this.val = val
    this.next = null
};

var MyLinkedList = function() {
    this.dummy = new listNode()
    this.tail = this.dummy
    this.length = 0
};


/**
* 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.getPreNode = function(index) {
    if (index < 0 || index >= this.length) {
      return -1;
    }
    // 初始化front与back，分别一前一后
    let front = this.dummy.next
    let back = this.dummy
    // 在查找的时候，front与back总是一起走
    for (let i = 0; i < index && front != null; i++) {
      back = front;
      front = front.next;
    }
    // 把back做为prev并且返回
    return back
};

MyLinkedList.prototype.get = function(index) {
    if (index < 0 || index >= this.length) {
      return -1;
    }
    
    return this.getPreNode(index).next.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
    const p = new listNode(val)
    // 将p.next指向第一个结点
    p.next = this.dummy.next;
    // dummy.next指向新结点，使之变成第一个结点
    this.dummy.next = p;
    // 注意动静结合原则，添加结点时，注意修改tail指针。
    if (this.tail == this.dummy) {
      this.tail = p;
    }
    // 链表长度+1
    this.length ++
};

/**
* Append a node of value val to the last element of the linked list. 
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtTail = function(val) {
    // 尾部添加一个新结点
    this.tail.next = new listNode(val)
    // 移动tail指针
    this.tail = this.tail.next;
    // 链表长度+1
    this.length ++
};

/**
* 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.length) {
    // Case 1.如果 index 大于链表长度，则不会插入结点。
    return;
  } else if (index == this.length) {
    // Case 2.如果 index 等于链表的长度，则该结点将附加到链表的末尾。
    this.addAtTail(val);
  } else if (index <= 0) {
    // Case 3. 如果index小于0，则在头部插入结点。
    this.addAtHead(val);
  } else {
    // Case 4.
    // 得到index之前的结点pre
    const pre = this.getPreNode(index);
    // 在pre的后面添加新结点
    const p = new listNode(val);
    p.next = pre.next;
    pre.next = p;
    // 链表长度+1
    this.length++;
  }
};

/**
* Delete the index-th node in the linked list, if the index is valid. 
* @param {number} index
* @return {void}
*/
  
  
MyLinkedList.prototype.deleteAtIndex = function(index) {
  // Case 1. 如果index无效，那么什么也不做。
  if (index < 0 || index >= this.length) {
    return;
  }
  // Case 2. 删除index结点
  // step 1. 找到index前面的结点
  const pre = this.getPreNode(index);
  // step 2. 如果要删除的是最后一个结点，那么需要更改tail指针
  if (this.tail == pre.next) {
    this.tail = pre;
  }
  // step. 3 进行删除操作。并修改链表长度。
  pre.next = pre.next.next;
  this.length--;
};

/** 
* 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)
*/

如果不使用哑结点，而直接初始化head，代码如下：

/**
 * Initialize your data structure here.
 */
var MyLinkedList = function() {
  this.head=null
  this.rear=null
  this.len=0
};
function ListNode(val) {
  this.val = val;
  this.next = 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.get = function(index) {
  if(index<0||index>this.len-1)
    return -1
  var node=this.head
  while(index-->0){
    if(node.next==null)
      return -1
    node=node.next
  }
  return node.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) {
  var node=new ListNode(val)
  if(this.head==null)
    this.rear=node
  else
    node.next=this.head
  this.head=node
  this.len++
};

/**
 * Append a node of value val to the last element of the linked list. 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
  var node=new ListNode(val)
  if(this.head==null)
    this.head=node
  else
    this.rear.next=node
  this.rear=node
  this.len++
};

/**
 * 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<=0)
    return this.addAtHead(val)
  if(this.len<index)
    return
  if(index==this.len)
    return this.addAtTail(val)
  var node=this.head
  while(index-->1){
    node=node.next
  }
    
  var newnode=new ListNode(val)
  newnode.next=node.next
  node.next=newnode
  this.len++
};

/**
 * 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.len-1||this.len==0)
    return
  if(index==0){
    this.head=this.head.next
    this.len--
    return
  }

  var node=this.head
  var myindex=index
  while(index-->1){
    node=node.next
  }
  if(myindex==(this.len-1)){
    this.rear=node
  }
  node.next=node.next.next
  this.len--
};

/**
 * 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)
 */

这两段代码一对比就能看出来，使用哑结点会简洁很多。

3. 经典题目：链表的属性

（1）环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false

解释：链表中没有环。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

我们只需要对每个遍历过的节点进行标记（因为这里每个节点都是一个对象，所以相当于遍历这个节点时，给他设置一个flag属性，如果在此遍历到的节点存在这个属性说明形成了环），后面如果再遇到它，说明有环，就直接返回true：

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    while(head){
        if(head.flag){
            return true
        }else{
            head.flag = true
            head = head.next
        }
    }
    return false
};

复杂度分析：

• 时间复杂度：O(n)，其中n是链表的节点数，最差坏的情况下我们要遍历完整个链表；
• 空间复杂度：O(n)，其中n是链表的节点数，主要为哈希表的开销，最坏情况下需要将每个节点插入到哈希表中一次。

（2）环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

进阶：你是否可以不用额外空间解决此题？

和上面一题的思路一样，都是设置一个flag，只是返回值不一样，最后指向的是有flag 的节点，所以直接返回head即可。

上述方法需要开辟O(n)的储存空间来储存标记信息，那我们尝试用快慢指针来解决这个问题： 设置两个指针，快指针每次走两个节点，慢指针每次走一个节点，如果存在环，那么两个指针一定相遇。等快慢指针相遇之后，我们在用另一个指针，去寻找他们相遇的位置就可以了。

设置标识法：

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    while(head){
        if(head.flag){
            return head
        }else{
            head.flag = true
            head = head.next
        }
    }
    return null
};

快慢指针法：

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let fast = head
    let slow = head
    let cur = head

    while(fast && fast.next && fast.next.next){
        slow = slow.next
        fast = fast.next.next
        if(fast == slow){
            while(cur!=slow){
                cur = cur.next
                slow = slow.next
            }
            return slow
        }
    }
    return null
};

设置标识法复杂度分析：

• 时间复杂度：O(n)，其中n是链表的节点数，最差坏的情况下我们要遍历完整个链表；
• 空间复杂度：O(n)，其中n是链表的节点数，主要为哈希表的开销，最坏情况下需要将每个节点插入到哈希表中一次。

快慢指针法复杂度分析：

• 时间复杂度：O(n)，其中n是链表中节点数。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O(N)+O(N)=O(N)。
• 空间复杂度：O(1)。我们只使用了 slow、fast、cur 三个指针。

（3）相交链表

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

示例 2：

示例 3：

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

一个比较直接直接的方法就是用双指针来解决，思路就是将链表拼成ab和ba这样就消除了两者的高度差，如果a和b有相交的部分，那么ab和ba也一定有相交的部分。具体实现步骤如下：

• 定义两个指针 pA 和 pB；
• pA 从链表 a 的头部开始走，走完后再从链表 b 的头部开始走；
• pB 从链表 b 的头部开始走，走完后再从链表 a 的头部开始走；
• 如果存在相交的点就直接返回pA或者pB

/**
 * 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) {
    let pA = headA
    let pB = headB
    while(pA !== pB){
        pA = pA === null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }
    return pA
};

复杂度分析：

• 时间复杂度：O(m + n) ，其中m和n分别是两个链表的节点数，最差情况下需要遍历完两个链表。
• 空间复杂度：O(1)，节点指针 A , B 使用常数大小的额外空间。

（4）链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示： 给定链表的结点数介于 1 和 100 之间。

对于这种求链表的中间点的题，我们可以使用快慢指针来实现，初始化slow和fast两个指针，开始时两个指针都指向头结点。然后慢指针一次走一步，快指针一次走两步，这样快指针走完整个链表时，慢指针正好走到链表的中间。

在遍历的过程中，如果快指针的后一个节点为空，就结束遍历，返回慢指针的值。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let fast = head, slow = head

    while(fast && fast.next){
        slow = slow.next
        fast = fast.next.next
    }
    return slow
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是给定链表的结点数目。
• 空间复杂度：O(1)，只需要常数空间来存放 slow 和 fast 两个指针。

（5）回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

1）字符串拼接： 对于这道题，最直接的思路就是，遍历链表，同时正向和反向拼接链表的节点，最后比较两个拼接出来的字符串是否一样。**

2）递归遍历：

• 首先，定义一个全局的指针pointer，其初始值为head，用来正序遍历
• 然后，调用递归函数，对链表进行逆序遍历，当头部节点为null的时候停止遍历
• 如果正序遍历的节点值和逆序遍历的节点值都相等，就返回true，否则就返回false

1）字符串拼接：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    let a = ""
    let b = ""
    while(head){
        const nodeVal = head.val
        a = a + nodeVal
        b = nodeVal + b
        head = head.next
    }
    return a === b
};

递归遍历：

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


let pointer
function fn(head) {
    if(!head) return true
    const res = fn(head.next) && (pointer.val === head.val)

    pointer = pointer.next
    return res
} 

var isPalindrome = function(head) {
    pointer = head
    return fn(head)
};

字符串拼接复杂度分析：

• 时间复杂度：O(n)，其中 n 指的是链表的元素个数，我们需要遍历完整个链表。
• 空间复杂度：O(1)，这里只需要常量的空间来保存两个拼接的字符串。

递归遍历复杂度分析：

• 时间复杂度：O(n)，其中 n 指的是链表的大小。
• 空间复杂度：O(n)，其中 n 指的是链表的大小，最差的情况下递归栈的深度为n。

（6）链表组件

给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 G，该列表是上述链表中整型值的一个子集。返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。

示例 1：

输入:
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释:
链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。

示例 2：

输入:
head: 0->1->2->3->4
G = [0, 3, 1, 4]
输出: 2
解释:
链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。

提示：

• 如果 N 是给定链表 head 的长度，1 <= N <= 10000。
• 链表中每个结点的值所在范围为 [0, N - 1]。
• 1 <= G.length <= 10000
• G 是链表中所有结点的值的一个子集.

对于这道题目。有两个关键点：

• 组件必须是链表中的连续节点
• 在G中包含连续节点的每个数值，如果出现不连续，结果就+1

根据这两点，我们可以定义一个表示，这里暂且定义名为isComponent，如果当前G中有这个值，并且isComponent是false，就说明这是一个新的组件，结果加一，如果G中不存在这个值，直接将isComponent置位false，将指针向后移动一位，继续遍历。只要当前指针存在，就一直遍历，直到遍历完整个链表。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number[]} G
 * @return {number}
 */
var numComponents = function(head, G) {
    let cur = head
    let isComponent = false
    let res = 0

    while(cur){
        if(G.indexOf(cur.val) > -1){
            if(!isComponent){
                isComponent = true
                res++
            }
        }else{
            isComponent = false
        }
        cur = cur.next
    }
    return res
};

复杂度分析：

• 时间复杂度：O(m+n)，这里需要遍历完整个整个链表和数组，所以时间复杂度为O(m+n)，其中m是链表的元素个数，n是G的元素个数；
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（7）链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 2 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

对于这个题目，我们可以使用快慢指针来解决，初始化slow和fast两个指针，开始时两个指针都在链表的头部。

首先让快指针fast先走，向后走k个节点，这样快指针和慢指针之间就相差k个节点。之后，两个指针同时向后移动，知道快指针移动到最后一个节点。这时，由于快慢指针之间相差k个节点，所以此时慢指针所指向的节点就是倒数第k个节点。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let slow = head, fast = head;
    let cur = 0;
    while(cur < k){
        fast = fast.next
        cur++
    }

    while(fast){
        fast = fast.next
        slow = slow.next
    }
    return slow

};

复杂度分析：

• 时间复杂度： O(n)，其中n是链表的节点数，我们需要遍历整个链表；
• 空间复杂度： O(n)，其中n是链表的节点数，我们需要储存快慢两个指针指向的链表；

4. 经典题目：链表的操作

（1）两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

这是一个链表操作的题目，我们可以遍历两个链表，将每个节点依次相加。得到相加的结果之后，将个位数作为当前位的结果，如有十位，就将十位进到下一次进行相加，这样就得出的最后的结果。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    const l3 = new ListNode(0)  // 用来保存结果的链表
    let p1 = l1 //定义两个指针，来遍历链表
    let p2 = l2
    let p3 = l3 //定义两个指针，指向结果链表
    let carry = 0  // 记录每次相加之后的进位的值
    while(p1 || p2){
        const v1 = p1 ? p1.val : 0
        const v2 = p2 ? p2.val : 0 
        const val = v1 + v2 + carry // 
        carry = Math.floor(val/10)  // 计算进位的值
        p3.next = new ListNode(val % 10) // 将个位的值作为当前位的结果
        if(p1) p1 = p1.next   // 将指针指向下一个节点
        if(p2) p2 = p2.next
        p3 = p3.next
    }
    // 如果最后还有进位的值，直接放在结果链表
    if(carry){
        p3.next = new ListNode(carry)
    }
    return l3.next
};

复杂度分析：

• 时间复杂度：O(max(m, n))，其中 m 与 n 分别为两个链表的长度，我们需要遍历每个链表。
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（2）两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶： 如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

对于这道题目，我们可以先用两个栈分别将两个链表的元素push存储起来，然后再从个位开始将两个数组对应的元素相加即可，详细步骤如下：

• 初始化stack1和stack2两个栈，并遍历两个链表，将链表元素存储起来；
• 初始化一个空的节点dummyHead来储存新的链表的值；
• 遍历两个栈，从栈的最后分别取元素，进行相加，超过10的部分进行进位，小于10的部分就作为当前点的和，放在结果链表dummyHead中
• 当两个栈都为空的时候，结束遍历
• 最后判断一下，如果最后一次相加之后还有进位值，记得加在链表上

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let stack1 = [], stack2 = [];

    while(l1){
        stack1.push(l1)
        l1 = l1.next
    }
    while(l2){
        stack2.push(l2)
        l2 = l2.next
    }

    let dummyHead = {next: null}
    let carry = 0

    while(stack1.length || stack2.length){
        let p1 = stack1.pop()
        let p2 = stack2.pop()

        let x = p1 ? p1.val : 0
        let y = p2 ? p2.val : 0

        let sum = x + y + carry
        let m = sum % 10   //个位
        let n = Math.floor(sum / 10)
        dummyHead.next = { val: m, next: dummyHead.next}
        carry = n
    }

    if(carry){
        dummyHead.next =  { val: carry , next: dummyHead.next };
    }
    return dummyHead.next
};

复杂度分析：

• 时间复杂度：O(max(m, n))，其中 m 与 n 分别为两个链表的长度，我们需要遍历每个链表。
• 空间复杂度：O(m + n)，其中 m 与 n 分别为两个链表的长度，这是把链表内容放入栈中所用的空间。

（3）反转链表

反转一个单链表。示例:

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

进阶：你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

对于链表的操作，实际上我们是在操作链表的指针。所以，对于这道题，最直接的方法就是将每个节点的指针指向该节点的前驱节点，这样整个链表就反转过来了，需要设置三个指针：分别指向前驱节点，当前节点，后驱节点。

再尝试着使用递归来实现这个题目：

对于这道题来说，最重要的就是反转的操作：当前节点是head，那下一个节点就是head.next,我们只要将head.next指向head，就实现了反转。最后只要将head和head.next之间的指针断开，就实现了两个节点之间的指针反转。最后在递归执行以上步骤即可。

设置前驱节点:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // 设置指针指向前驱节点和当前节点
    let pre = null
    let cur = head
    // 遍历链表，直到链表节点为空
    while (cur!= null){
        // 记录当前的节点，用于后面的遍历
        let next = cur.next
        // 调转链表的指针方向
        cur.next = pre
        // 向后移动指针
        pre = cur
        cur = next
    }
    return pre
};

递归遍历：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // 首先判断链表为空或者只有一个节点的情况
    if(!head || !head.next){
        return head
    }
    // 储存下一个节点，便于后面进行递归
    let next = head.next
    // 递归
    let result = reverseList(next)
    // 断开当前节点和它的后驱节点
    head.next = null 
    // 把后面的节点作为当前的节点
    next.next = head
    return result
};

设置前驱节点复杂度分析：

• 时间复杂度：O(n)，其中n是链表的节点数，我们需要遍历整个链表；
• 空间复杂度：O(1)，这里我们只需要常量空间来储存指针。

递归遍历复杂度分析：

• 时间复杂度：O(n)，其中n是链表的节点数；
• 空间复杂度：O(n)，其中n是链表的节点数，在最差的情况下递归栈的深度为n。

（4）反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明：1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

这个题最主要的就是将第m到n的节点进行反转，然后将m-1节点指向n，让n+1节点指向m，这样就实现了链表的局部反转。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function(head, m, n) {
   // 定义虚拟头结点
   let dummy = new ListNode()
   dummy.next = head
   // 寻找第m-1节点
   let p = dummy
   for(let i =0; i<m-1; i++){
       p= p.next
   }
   // 定义当前节点和前驱节点，当前节点指向m节点
   let pre = null 
   let cur = p.next
   // 将m到n的节点进行反转
   for(let i = 0; i<= n-m; i++){
       let next = cur.next
       cur.next = pre
       pre = cur
       cur = next
   }
   // 将反转的局部链表和原链表进行拼接
   p.next.next = cur
   p.next = pre
   
   return dummy.next
};

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的节点数。在最坏情况下，需要遍历整个链表。

• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（5）旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

对于这道题目，一个很直接的思路就是将单链表转化为一个环形链表，然后移动完成之后再将链表断开为单链表，实现步骤主要是三步：

• 首先遍历链表，找到链表的尾结点，将尾结点和头结点连起来，这样就形成了一个环形链表；
• 题目说的右移k步，这里我们让尾结点左移，相当于往左移动length-k步；
• 最后，移动完成之后，找到链表的尾结点，将环形链表断开为单向链表。

/**
 * 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} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if(!head || !head.next){
        return head
    }
    // 找到尾结点，将单链表形成环形链表
    let tail = head
    let length = 1
    while(tail.next){
        length++
        tail = tail.next
    }
    tail.next = head
    // 尾结点进行移动
    k = k % length
    for(let i = 0; i < length - k; i++){
        tail = tail.next
    }
    // 找到头结点，断开环形链表
    head = tail.next
    tail.next = null
    return head
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是链表中节点的个数；
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（6）K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明：

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

一个思路就是使用递归求解：

• 启用一个计数器，截出链表的前k个节点
• 将链表进行反转
• 将上一次遍历时最后的节点，作为当前的开始节点，进行递归操作

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    let cur = head
    let count = 0

    while(cur !== null && count !== k){
        cur = cur.next
        count++
    }

    if(count == k){
        cur = reverseKGroup(cur, k)
        // 翻转链表
        while(count !== 0){
            count-- 
            let tmp = head.next
            head.next = cur
            cur = head
            head = tmp
        }
        head = cur
    }
    return head
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是链表中节点的个数；
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（7）两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）

对于这道题目，可以使用迭代和递归的方式：

（1）递归实现 在递归的过程中，其终止条件就是链表中没有节点了，或者链表中只有一个节点，不能再进行交换了。

对于链表中的两个节点，在两两交换之后，原来的链表头结点变成了第二个节点，原来的第二个节点就变成了新的头结点，其余节点的交换就可以通过递归来实现。

（2）迭代实现 对于迭代的方式，我们可以创建一个哑结点list，将这个节点指向题目给出的节点的头结点。初始化一个temp，用来保存这个哑结点，初始值为list，每次交换都交换temp后面的两个节点。 只有当temp节点之后有至少两个节点时，才能接续往后进行交换，否则结束交换。交换时，获取temp后面两个节点，更新节点的指针关系，来实现两个节点的交换。当两个节点交换完成之后，记得要更新temp节点为两两交换之后的第二个节点，即node1。

递归实现：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if(!head || !head.next){
        return head
    }
    const newHead = head.next  // 获取第二个节点
    head.next = swapPairs(newHead.next) // 将其余的节点进行递归交换
    newHead.next = head  // 完成节点的交换
    return newHead
};

迭代实现：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if(!head || !head.next){
        return head
    }
    const list = new ListNode(0)
    list.next = head

    let temp = list

    while(temp.next && temp.next.next){
        const node1 = temp.next
        const node2 = temp.next.next
        // node1 和 node2 进行交换
        temp.next = node2
        node1.next = node2.next
        node2.next = node1
        // 更新temp节点
        temp = node1
    }
    return list.next
};

递归的复杂度分析：

• 时间复杂度：O(n)，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。
• 空间复杂度：O(n)，其中 n 是链表的节点数量。空间复杂度主要取决于递归调用的栈空间。

迭代的复杂度分析：

• 时间复杂度：O(n)，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（8）交换链表中的节点

给你链表的头节点 head 和一个整数 k 。

交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[1,4,3,2,5]

示例 2：

输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出：[7,9,6,6,8,7,3,0,9,5]

示例 3：

输入：head = [1], k = 1
输出：[1]

示例 4：

输入：head = [1,2], k = 1
输出：[2,1]

示例 5：

输入：head = [1,2,3], k = 2
输出：[1,2,3]

提示：

• 链表中节点的数目是 n
• 1 <= k <= n <= 10
• 0 <= Node.val <= 100

对于这道题目，我们可以使用快慢指针来解决，具体实现思路如下：

• 初始化一个dummy哑结点，指向head，也就是在head之前放一个空节点，这样就避免了越界，少了一些指针为空的判断；
• 初始化slow和fast两个快慢指针，初始时都指向哑结点dummy，并出初始化一个cur指针，用来之后保存第k个值；
• 首先让快指针和cur移动k步，慢指针保持不动，这样此时，cur指向的就是第k个值，快慢指针之间隔着k步；
• 让快慢指针一起走，直到快指针走到头为止，由于两者之间隔着k步，所以此时慢指针指向倒数第k个节点
• 将此时慢指针指向的元素，也就是倒数第k个元素和cur元素，也就是第k个元素进行交换；
• 最后返回链表头结点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
 * @param {number} k
 * @return {ListNode}
 */
var swapNodes = function(head, k) {
    let dummy = new ListNode(0)
    dummy.next = head

    let i = 0, cur = dummy
    let slow = dummy, fast =dummy

    while(i++ < k){
        fast = fast.next
        cur = cur.next
    }

    while(fast){
        fast = fast.next
        slow = slow.next
    }

    let temp = cur.val
    cur.val = slow.val
    slow.val = temp

    return head
};

复杂度分析：

• 时间复杂度：O(n)。其中n为链表的长度，最坏的情况下，我们需要遍历整个链表。
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（9）分隔链表

给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。

示例：

输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5

对于这道题目，一个很直接的思路就是初始化两个链表，一个链表来存储小于x的值，另一个链表来存储大于x的值。

这里还初始化了两个链表：mallHead 和 largeHead。这两个是链表的哑节点，即它们的 next 指针指向链表的头节点，这样做的目的是为了更方便地处理头节点为空的边界条件。

遍历结束后，将 large 的 next 指针置空，这是因为当前节点复用的是原链表的节点，而其 next 指针可能指向一个小于 x 的节点，我们需要切断这个引用。同时将 small 的 next 指针指向 largeHead 的 next 指针指向的节点，即真正意义上的 large 链表的头节点。最后返回 smallHead 的 next 指针就是最后的答案。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    let small = new ListNode(0)
    const smallHead = small
    let large = new ListNode(0)
    const largeHead = large

    while(head){
        if(head.val < x){
            small.next = head
            small = small.next
        }else{
            large.next = head
            large = large.next
        }
        head = head.next
    }

    large.next = null
    small.next = largeHead.next
    return smallHead.next
};

复杂度分析：

• 时间复杂度: O(n)，其中 n 是原链表的长度，因为对该链表进行了一次遍历。
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（10）分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ] ** 示例 1：

输入:
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。

示例 2：

输入:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:
输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。

提示:

• root 的长度范围： [0, 1000].
• 输入的每个节点的大小范围：[0, 999].
• k 的取值范围： [1, 50].

对于这道题目，我们可以先计算链表的长度length，尽可能均分链表。然后再计算每个子链表的长度：先计算平均每个子链表的长度为length/k，倘若不能整除，剩余的length%k个元素，则前length%k个子链表的长度再加一。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} root
 * @param {number} k
 * @return {ListNode[]}
 */
var splitListToParts = function(root, k) {
    let cur = root
    let length = 0
    while(cur){
        cur = cur.next
        length++
    }
    // 每一项的长度
    let width = Math.floor(length / k), curry = length % k
    let num, temp
    
    let res = new Array(k);
    for(let i = 0; i < k; i++) {
        // 计算从剩余链表中截取的长度
        num = i < curry ? width + 1 : width
        // 从剩余链表中截取num个元素
        temp = cur = root;
        for(let j = 1; cur && j < num; j++) {
            cur = cur.next;
        }
        // 修改root指向
        if(cur) {
            root = cur.next;
            cur.next = null;
        } else {
            root = null;
        }
        res[i] = temp;
    }
    return res
};

复杂度分析：

• 时间复杂度：O(N + k)，N 指的是链表的结点数，若 k 很大，则还需要添加许多空列表。
• 空间复杂度：O(max(N, k))，存放答案所需的空间。

（11）重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

这个题目的一个思路就是：

• 首先使用快慢两个指针，获取链表的中点
• 从链表的中点断开，慢指针指向前半个链表，快指针指向后半个链表
• 将后半个链表进行翻转，让快指针重新指向翻转后的后半个链表
• 按照题目要求的规则将两个链表的节点添加在一起

/**
 * 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 {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    if(!head || !head.next) return 
    let slow = head
    let fast = head
    
    // 获取链表的中间节点
    while(fast && fast.next){
        slow = slow.next
        fast = fast.next.next ? fast.next.next : null
    }
    
    // 将链表从中点断开，fast指向后半个链表，slow指向前半个链表
    fast = slow.next
    slow.next = null
    slow = head
    
    // 反转链表后半部分
    let pre = null
    let cur = fast
    while(cur){
        let temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    }

    // 将fast指向后半段反转后的链表
    fast = pre

    // 将两个链表按照要求进行合并
    while(fast){
        let slowNext = slow.next
        let fastNext = fast.next

        slow.next = fast
        fast.next = slowNext
        slow = slowNext
        fast = fastNext
    }
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是链表中节点的个数，我们需要遍历整个链表；
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（12）排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

（1）归并排序： 题目要求在O(n log n) 时间复杂度和常数级空间复杂度下对链表进行排序，恰好归并排序可以满足要求。

其主要思路如下：

• 先判断链表是否只有一个元素，若是则直接返回
• 使用快慢指针，找到链表的中间节点
• 对链表的前半部分和后半部分分别递归的进行归并排序
• 最后将两个子链表进行合并

（2）借助数组来实现： 我们可以借助数组来实现这个题目，将链表转化为数组，对数组的元素进行排序。排序完成之后，将数组再转化为链表。

归并排序：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    // 若为空链表或只有一个节点，就直接返回
    if(head === null || head.next === null){
        return head
    }
    // 使用快慢指针获取链表的中间值
    let fast = head
    let slow = head
    while(slow.next && fast.next && fast.next.next){
        slow = slow.next
        fast = fast.next.next
    }
    // 将链表分成两个
    const middle = slow.next
    slow.next = null
    
    // 对左右的两个链表分别递归的进行归并排序
    const left = head
    const right = middle
    return merge(sortList(left), sortList(right))
};

function merge (left, right) {
    // 初始化一个空的结果节点
    let res = new ListNode(null);
    // 当前节点
    let prev = res;   
    while (left && right) {
        // 如果左边的值小于右边的值，当前节点指向左节点，左节点指向下一个节点
        if (left.val < right.val) {
            [prev.next, left] = [left, left.next]
        }else {
        // 如果右边的值小于左边的值，当前节点指向右节点，右节点指向下一个节点
            [prev.next, right] = [right, right.next];
        }
        // 当前节点指向下一个节点
        prev = prev.next;
    }
    // 如果还有剩余的节点，就直接拼接在结果链表的最后
    prev.next = left ? left : right;
    return res.next;
}

借助数组实现：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    if(head === null || head.next === null){
        return head
    }
    let cur = head
    let index = 0
    const arr = []
    // 将链表转化为数组
    while(cur){
        arr[index] = cur.val
        cur = cur.next
        index ++
    }
    // 对数组进行排序
    arr.sort((a,b) => a-b)
    // 将数组转化为链表
    cur = head
    index = 0
    while(cur){
        cur.val = arr[index]
        index ++
        cur = cur.next
    }
    return head
};

归并排序复杂度分析：

• 时间复杂度：O(n)，其中 n 是链表中节点的个数，我们需要遍历整个链表；
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

借助数组复杂度分析：

• 时间复杂度：O(n)，其中 n 是链表中节点的个数，我们需要遍历整个链表；
• 空间复杂度：O(n)，其中n是数组的长度。

（13）移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

• 列表中的节点在范围 [0, 10] 内
• 1 <= Node.val <= 50
• 0 <= k <= 50

对于这道题目，本身是很简单的，就是遍历链表，删除指定的值，但是需要注意，如果是需要删除的值在链表中时，直接删除即可，如果要删除的节点在链表的头部，这就要处理遍历情况，为了避免这种情况，我们可以初始化一个哑结点dummyHead，它是一个空节点，将他放在头结点的前面。这样就不会出现为空的情况。

/**
 * 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} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    let dummyHead = new ListNode(0)
    dummyHead.next = head

    let pre = dummyHead, cur = head
    while(cur){
        cur.val == val ? pre.next = cur.next : pre = cur
        cur = cur.next
    }
    return dummyHead.next
};

复杂度分析：

• 时间复杂度：O(n)。其中n为链表的长度，我们需要遍历整个链表。
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（14）删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

这是一道简单的题目，CURD是链表的基本操作，我们只要对比两个相邻的节点，如果值相等，就将删除一个元素，如不相等就直接向后移动指针，重复行上述步骤，直到遍历完链表的所有节点为止。

/**
 * 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 deleteDuplicates = function(head) {
    let cur = head

    while(cur && cur.next){
        if(cur.val === cur.next.val){
            cur.next = cur.next.next
        }else{
            cur = cur.next
        }
    }
    return head
};

复杂度分析：

• 时间复杂度：O(n)。其中n为链表的长度，我们需要遍历整个链表。
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（15）删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

输入: 1->1->1->2->3
输出: 2->3

和上面一道思路相似，但是这个题目需要考虑更多的内容。

我们在删除节点时，需要把节点的前驱结点和后驱节点都删除掉。我们想要获取一个节点的前驱节点，就需要设置一个虚拟的头结点来实现，虚拟的头结点指向真正的头结点，这样就确保每个节点都有前驱结点。

需要注意的是，重复的节点可能不只有两个，所以，我们还需要往后验证，反复进行判断和删除操作，直到没有重复的元素为止。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    // 处理链表只有0或1个节点的情况
    if(!head||!head.next){
        return head
    }
    // 设置虚拟头节点
    let dummy = new ListNode()
    dummy.next = head
    // 设置当前节点
    let cur = dummy

    while (cur.next &&cur.next.next){
        if(cur.next.val === cur.next.next.val){
            // 保存重复节点的值
            let val =cur.next.val
            // 反复判断是否还有相等的节点
            while(cur.next &&cur.next.val === val)
            {
                cur.next = cur.next.next
            }
        }else{
            cur = cur.next
        }
    }
    // 返回最终结果，也就是链表的起始的节点
    return dummy.next
};

复杂度分析：

• 时间复杂度：O(n)。其中n为链表的长度，我们需要遍历整个链表。
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（16）删除链表的倒数第 N 个结点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：给定的 n 保证是有效的。 进阶：你能尝试使用一趟扫描实现吗？

本题中，我们可以使用比较暴力的方法，遍历两遍链表，第一遍计算出链表的长度，第二遍删除倒数第N个元素，但是这样势必会使得执行效率很低，我们需要考虑只遍历一遍的方法。

如果只遍历一遍，那么我们就需要用上双指针来解决这个问题。这里我们使用快慢指针：

• 先设置快和慢两个指针，开始的时候都指向虚拟的头结点
• 让快指针先走，走到第N个节点
• 然后两个指针一起走，直到快指针指导最后一个节点
• 这时，慢指针指向的节点就是链表的倒数第N个节点
• 删除对应节点即可

最重要的是，快指针和慢指针一直保持相隔N个节点，这样就容易后面的操作。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
   // 设置虚拟头结点
   const dummy = new ListNode()
   dummy.next = head
   // 设置快慢指针
   let fast = dummy
   let slow = dummy
   // 快指针先走到第N个节点
   while (n!==0){
       fast = fast.next
       n--
   }
   // 快慢指针一起走，直到快指针指向最后一个节点
   while (fast.next){
       fast = fast.next
       slow = slow.next
   }
   // 删除倒数第N个节点
   slow.next = slow.next.next
   return dummy.next
};

复杂度分析：

• 时间复杂度：O(n)。其中n为链表的长度，我们需要遍历整个链表。
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（17）合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

实际上，处理链表也就是在处理链表之间的指针的关系，这些指针就像是一条线一样，将所有的数据穿在一起，形成了一条链表。

我们只需要每次对两个链表的节点进行对比，然后让当前指针指向相对较小的数，然后将指针指向调整到指向的数的后面，这样依次对比完两个节点，就可以实现两个链表的有序合并。

需要注意的是，我们需要考虑链表长度不同的情况，由于两个链表都是有序链表，如果有一条链表遍历完了，另外一条链表没有遍历完，就直接将没遍历完的部分放在新链表最后就可以了。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    // 定义新链表的头结点
    let head = new ListNode();
    // 当前指针指向的节点
    let cur = head;

    while (l1&&l2){
        if(l1.val<=l2.val){
            // 先指向只较小的节点 
            cur.next = l1
            // 在将指针的指向移动
            l1 = l1.next
        }else{
            cur.next = l2
            l2 = l2.next
        }
        // 连接好一个节点之后，指针的方向也会移动一位
        cur = cur.next
    }
    // 处理两个链表长度不同的情况
    cur.next = l1!==null ? l1 : l2
    // 返回最后的结果，头指针指向的那个位置，就代表新生成的链表
    return head.next
};

复杂度分析：

• 时间复杂度：O(n + m)。其中m和n分别为两个链表的长度，我们需要遍历两个链表。
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。

（18）合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

对于这道题目，我们可以每次合并两个链表，合并完成之后，更新数组，继续两两合并，使用递归完成合并即可。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    let len = lists.length
    if(!len){
        return null
    }
    if(len === 1){
        return lists[0]
    }
    // 将数组的前两项先进行合并
    let res = mergeTwoKLists(lists[0], lists[1])
    // 更新数组
    lists.splice(0, 2, res)
    // 进行递归操作
    return mergeKLists(lists)
};

// 合并两个链表
function mergeTwoKLists(l1, l2){
    let head = new ListNode(), pre = head
    while (l1 && l2) {
        if (l1.val > l2.val) {
            pre.next = l2
            l2 = l2.next
        } else {
            pre.next = l1
            l1 = l1.next
        }
        pre = pre.next
    }
    pre.next = l1 ? l1 : l2
    return head.next
}

复杂度分析：

• 时间复杂度：O(NlogK)，K 条链表的总结点数是 N，平均每条链表有 N/K 个节点，因此合并两条链表的时间复杂度是 O(N/K)。从 K 条链表开始两两合并成一条链表，因此每条链表都会被合并 logK、 次，因此 K条链表会被合并 K * logK 次，因此总共的时间复杂度是 K * logK * N/K 即 O(NlogK)。
• 空间复杂度：O(1)，没有用到与 K 和 N 规模相关的辅助空间，故渐进空间复杂度为 O(1)。

（19）复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。 返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

• 0 <= n <= 1000
• -10000 <= Node.val <= 10000
• Node.random 为空（null）或指向链表中的节点。

对于这道题目，我们可以用三步走来搞定：

1）第一步，根据遍历到的原节点创建对应的新节点，每个新创建的节点是在原节点后面，比如下图中原节点1不再指向原原节点2，而是指向新节点1

2）第二步是最关键的一步，用来设置新链表的随机指针

上图中，可以看到一个规律

• 原节点1的随机指针指向原节点3，新节点1的随机指针指向的是原节点3的next
• 原节点3的随机指针指向原节点2，新节点3的随机指针指向的是原节点2的next

也就是，原节点i的随机指针(如果有的话)，指向的是原节点j。那么新节点i的随机指针，指向的是原节点j的next。

3）第三步只要将两个链表分离开，再返回新链表就可以了

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    if(!head){
        return null
    }

    let p = head
    // 在每个原节点后面创建一个新节点
    while(p !== null){
        let newNode = new Node(p.val)
        newNode.next = p.next
        p.next = newNode
        p = newNode.next
    }
    p = head
    // 设置新节点的随机节点
    while(p !== null){
        if(p.random){
            p.next.random = p.random.next
        }
        p = p.next.next
    }
    let dummyHead = new Node(-1)
    p = head
    let cur = dummyHead
    // 将两个链表分离
    while(p !== null){
        cur.next = p.next
        cur = cur.next
        p.next = cur.next
        p = p.next
    }
    return dummyHead.next
};

复杂度分析：

• 时间复杂度：O(n)，其中 n 是链表中节点的数目，我们需要遍历整个链表。
• 空间复杂度：O(n)，这里我们只需要常量的空间。

（20）对链表进行插入排序

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4

示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

对于单向链表而言，只有指向后一个节点的指针，因此需要从链表的头节点开始往后遍历链表中的节点，寻找插入位置。对链表进行插入排序的具体过程如下:

1. 首先判断给定的链表是否为空，若为空，则不需要进行排序，直接返回。
2. 创建哑节点 dummyHead，令 dummyHead.next = head。引入哑节点是为了便于在 head 节点之前插入节点。
3. 维护 last 为链表的已排序部分的最后一个节点，初始时 last = head。
4. 维护 cur 为待插入的元素，初始时 cur = head.next。
5. 比较 last 和 cur 的节点值。

• 若 last.val <= cur.val，说明 cur 应该位于 last 之后，将 last后移一位，curr 变成新的 last。
• 否则，从链表的头节点开始往后遍历链表中的节点，寻找插入 cur 的位置。令 pre 为插入 cur 的位置的前一个节点，进行如下操作，完成对 cur 的插入：

last.next = cur.next
cur.next = pre.next
pre.next = cur

6. 令 cur = last.next，此时 cur 为下一个待插入的元素。
7. 重复第 5 步和第 6 步，直到 cur 变成空，排序结束。
8. 返回 dummyHead.next，为排序后的链表的头节点。

/**
 * 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 insertionSortList = function(head) {
    if(!head){
        return head
    }
    const dummyHead = new ListNode(0)
    dummyHead.next = head

    let last = head, cur = head.next

    while(cur){
        if(last.val <= cur.val){
            last = last.next
        }else{
            let pre = dummyHead
            while(pre.next.val <= cur.val){
                pre = pre.next
            }
            last.next = cur.next
            cur.next = pre.next
            pre.next = cur
        }
        cur = last.next
    }
    return dummyHead.next
};

复杂度分析：

• 时间复杂度：O(n)，对于链表而言，插入元素时只要更新相邻节点的指针即可，因此插入操作的时间复杂度是 O(1)，但是找到插入位置需要遍历链表中的节点，时间复杂度是 O(n)，因此链表插入排序的总时间复杂度仍然是 O(n)，其中 n 是链表的长度。
• 空间复杂度：O(1)，需要额外的常数大小的辅助空间。

（21）奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

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

示例 2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

• 应当保持奇数节点和偶数节点的相对顺序。
• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

这道题目的思路就是遍历链表，将链表的中的所有的元素分为a和b两个链表，分别用来保存奇数值和偶数值，遍历结束之后，偶数链表拼接在奇数链表后面。具体实现过程如下：

• 首先将链表节点数为0，1，2的情况排除掉，直接返回head
• 定义a和b两个链表，分别表示奇数和偶数节点，用node来暂时保存b链表的头结点，便于后面拼接
• 使用while循环对a和b链表进行交叉遍历赋值。a和b一直指向奇数链和偶数链的最后一个节点
• 将两个链表进行拼接，并返回

/**
 * 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 oddEvenList = function(head) {
    if(head === null || head.next === null || head.next.next === null){
        return head
    }
    let a = head       // 存放奇数节点
    let b = head.next  // 存放偶数节点
    const node = head.next   // 记录b链表的头节点
    while(b !== null && b.next !== null){
        a.next = b.next
        a = a.next
        b.next = a.next
        b = b.next
    }
    a.next = node
    return head
};

复杂度分析：

• 时间复杂度：O(n)。其中n为链表的长度，我们需要遍历整个链表。
• 空间复杂度：O(1)。需要额外的常数大小的辅助空间。