数据结构与算法之链表篇

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. LeetCode：链表的属性

（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：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA= 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Reference of the node with value = 2 输入解释：相交节点的值为 2（注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB= 2 输出：null 输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 解释：这两个链表不相交，因此返回 null。

注意：

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

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

• 定义两个指针 pA 和 pB；
• pA 从链表 a 的头部开始走，走完后再从链表 b 的头部开始走；
• pB 从链表 b 的头部开始走，走完后再从链表 a 的头部开始走；
• 如果存在相交的点就直接返回pA或者pB ```javascript /**
  • 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. LeetCode：链表的操作

  （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
};