zhang's - 链表 - 《leetcode》

移除链表元素">移除链表元素
- 题目描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
- 题解⌨
  - 1.迭代遍历
两数相加">两数相加
删除链表的倒数第 N 个结点">删除链表的倒数第 N 个结点
- 题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
- 题解⌨
  - 1.迭代(较优解👍)
  - 2.前后指针
反转链表 II⚠">反转链表 II⚠
- 题目：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。
- 题解⌨
  - 1. 穿针引线法

移除链表元素

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

🌰：

示例1：

链表 - 图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 输出：[]

题解⌨

1.迭代遍历

var removeElements = function (head, val) {
    if (!head) return head;
    let cur = head;
    while (cur.next) {
        if (cur.next.val === val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }
    if(head.val === val){
        head = head.next;
    }
    return head;
};

两数相加

题目：给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

🌰：

示例1：
```
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
```
```
输入：l1 = [0], l2 = [0]
输出：[0]
```
```
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
```
题解⌨

1.链表遍历，同一层级下的数据相加
```javascript const addTwoNumbers = function (l1, l2) { let cur1 = l1; let cur2 = l2; let result = new ListNode(0, null) let head = result while (cur1 || cur2) { let value = 0; if (cur1 && cur2) {
```
value = cur1.val + cur2.val
```
} else if (cur1) {
```
value = cur1.val
```
} else if (cur2) {
```
value = cur2.val
```
}

let curValue = (result.val + value) result.val = curValue % 10

cur1 = cur1 && cur1.next ? cur1.next : null
cur2 = cur2 && cur2.next ? cur2.next : null

let val = Math.floor(curValue / 10)

if (cur1 || cur2 || val > 0) {
  result.next = new ListNode(val, null)
  result = result.next
}

} return head };


---

<a name="KaJ2c"></a>
### [两两交换链表中的节点](https://leetcode.cn/problems/swap-nodes-in-pairs/)
<a name="JQ9RA"></a>
#### 题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
🌰：<br />![](https://cdn.nlark.com/yuque/0/2022/jpeg/22022275/1653744116781-15a8fe56-cfa5-4906-8f0f-3f1bd13ac0d1.jpeg#clientId=ufd5b0fd3-50d3-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=167&id=ueba1735f&margin=%5Bobject%20Object%5D&originHeight=222&originWidth=422&originalType=url&ratio=1&rotation=0&showTitle=false&status=done&style=none&taskId=ubeb0ab00-1b41-4dea-89f1-cdc096939f7&title=&width=317)

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

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

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

题解⌨

1.迭代

var swapPairs = function (head) {
  let newNode = new ListNode(0, null)
  newNode.next = head;
  let temp = newNode;
  while (temp.next && temp.next.next) {
    const node1 = temp.next
    const node2 = temp.next.next
    temp.next = node2
    node1.next = node2.next
    node2.next = node1
    temp = node1
  }
  return newNode.next
};

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

题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

🌰：
链表 - 图3

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

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

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

题解⌨

1.迭代(较优解👍)

先将链条进行反转，然后再反转回来，当节点的排序等于第n个时，从链条中删减该节点。

var removeNthFromEnd = function (head, n) {
  let pre = null
  let temp = head
  while (temp) {
      const next = temp.next
      temp.next = pre
      pre = temp
      temp = next
  }
  temp = pre
  pre = null
  while (temp) {
      if (n === 1) {
          const next = temp.next
          temp = next
      } else {
          const next = temp.next
          temp.next = pre
          pre = temp
          temp = next
      }
      n--
  }
  return pre
};

2.前后指针

var removeNthFromEnd = function (head, n) {
  let fast = head
  let newNode = new ListNode(0, null)
  newNode.next = head
  let cur = newNode
  while (--n) {
      fast = fast.next
  }
  while (fast.next) {
      fast = fast.next
      cur = cur.next
  }
  cur.next = cur.next.next
  return newNode.next
};

反转链表 II⚠

题目：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

🌰：
链表 - 图4

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

输入：head = [5], left = 1, right = 1
输出：[5]

题解⌨

1. 穿针引线法

链表 - 图5

首先，找出并记录我们的前置点preNode，而pre.next就是需要反转的链表的起始点记为leftNode，继续往后遍历找到反转链表的末尾点记为rightNode，并且其rightNode.next就是我们后置点succNode。将反转链表输入反转函数反转后，再进行拼接即可。 ```javascript var reverseBetween = function (head, left, right) { let dNode = new ListNode(0) dNode.next = head; let curNode = dNode; let preNode = curNode for (let i = 0; i < left - 1; i++) {
```
  preNode = preNode.next
```
} leftNode = preNode.next let rightNode = leftNode for (let i = 0; i < right - left; i++) {
```
  rightNode = rightNode.next
```
} let succ = rightNode.next rightNode.next = null const reverseNode = reverseList(leftNode) curNode = reverseNode; while (curNode.next) {
```
  curNode = curNode.next;
```
} curNode.next = succ; preNode.next = reverseNode; return dNode.next };

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

<a name="A1Q9k"></a>
##### 2. 头插法(较优解👍)
![](https://cdn.nlark.com/yuque/0/2022/png/22022275/1654692373643-b0ad412a-1e94-40ab-8a05-9a1c634590b9.png#clientId=uc3fb17ea-1ea6-4&crop=0&crop=0&crop=1&crop=1&from=paste&id=u880ae47c&margin=%5Bobject%20Object%5D&originHeight=1125&originWidth=1142&originalType=url&ratio=1&rotation=0&showTitle=false&status=done&style=none&taskId=u57ad4816-1189-4c8c-9886-c61b646d5b3&title=)

- 遍历链条记录前置点pre，以及起始点cur，逐个遍历需要反转的节点，并插到前置点的next。
```javascript
var reverseBetween = function (head, left, right) {
    let dNode = new ListNode(0)
    dNode.next = head;
    let pre = dNode;
    let cur = null;
    for (let i = 0; i < left - 1; i++) {
        pre = pre.next;
    }
    cur = pre.next;
    next = cur.next;
    let len = right - left;
    while (len--) {
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
        next = cur.next
    }
    return dNode.next;
};

链表