> For the complete documentation index, see [llms.txt](https://smilence-yu.gitbook.io/coding/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://smilence-yu.gitbook.io/coding/chapter-2-linked-list.md).

# Chapter 2: Linked List

## 知识解析

除特别注明外，本文都使用以下所示的singly linked list。

```python
class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
```

### 2.1  Singly Linked List 的基本操作规范

{% hint style="success" %}
Linked List的问题，核心在于操作 + 移动。\
\
先考虑一轮操作，需要哪些变量，比如 `prev`, `next`\
\
对应操作 `arr.push` ，对linked list有 `tail.next = curr` `tail = tail.next` \
对应移动 `idx += 1` ，对linked list有 `[current node] = [current node].next` ，如果有 `prev` 变量则有 `prev = prev.next` ，如果有 `next_node` 变量则有 `next_node = next_node.next`
{% endhint %}

{% hint style="danger" %}
在修改linked list时，注意“先连后断”的原则。先更改原先 next 为 null 的节点，更新其next之后，就可以更改本来指向其next的节点，以此类推，最后处理的节点是需要删除next而不是更改next的
{% endhint %}

**2.1.1** 注意corner case ( `curr == head`, `curr == tail` , 或 `curr == None` 。**凡是修改list但不改变每个node的value的操作，只需要考虑：谁的`next` 指针受到影响，那么就需要维护这些节点。**

```python
def delNode(prev: ListNode) -> None :
    prev.next = prev.next.next
```

{% hint style="warning" %}
链表不能向后访问，所以记录`prev`变量比记录`curr` 更普适，因为前者可以推出后者，而反之则不然。当前节点可以用`prev.next` 来表示，这样就不用维护两个变量。
{% endhint %}

**2.1.2 遍历Linked list时，每次循环内只对一个或一对节点进行题意中的操作。**（不要试图对下一个或者下一对进行操作）

> *e.g. Reverse the linked list and return the new head. (*[*LeetCode: Reverse Linked List* ](https://leetcode.com/problems/reverse-linked-list/)*)*

```python
def reverseList(self, head: ListNode) -> ListNode:
    # Of course, it can also be done with recursion/stack
    prev, curr = None, head
    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next

    return prev 
```

**2.1.3 处理两个长度未必相等的linked list的问题**，循环的条件一般用 `while node1 and node2` , 再处理剩下非空的那个list。

> *e.g Merge two sorted linked lists and return it as a new list.(*[*Leetcode: Merge Two Sorted Lists)*](https://leetcode.com/problems/merge-two-sorted-lists/)

### 2.2  涉及到对Linked List 头的操作

{% hint style="success" %}
对于涉及到Linked List头节点的操作，不妨用`dummy = ListNode(0) dummy.next = head`来避开处理head发生变化的情况，最后用`dummy.next` 作为头节点即可。
{% endhint %}

> *e.g. Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. (* [*LeetCode: Partition List* ](https://leetcode.com/problems/partition-list/)*)*

### 2.3 寻找特定节点的问题

{% hint style="success" %}
对于寻找list某个特定位置的问题，不妨用 runner technique：`chaser, runner = head, head;` `chaser`与`runner`以不同速率或不同起点前进，直到`runner`满足一定条件时，结果由这两个共同决定。
{% endhint %}

> *e.g.1 Find the middle point of the linked list*

```python
def middlePoint(head: ListNode) -> ListNode:
    chaser, runner = head, head
    while runner.next and runner.next.next:
        chaser = chaser.next
        runner = runner.next.next
    return chaser
```

> *e.g.2 Find the kth to last element of a singly linked list.* \
> *e.g.3 Given a circular linked list, return the node at the beginning of the loop. (*[*LeetCode: Linked List Cycle ii)*](https://leetcode.com/problems/linked-list-cycle-ii/)\
> *e.g.4 Given a list, rotate the list to the right by k places, where k is non-negative. (*[*Leetcode: Rotate List*](https://leetcode.com/problems/rotate-list/) *先查找，再拆分)*

## 模式识别

### 2.4 交换node的问题

{% hint style="success" %}
 交换两个node，有且仅有这两个node以及他们prev node的next指针会受到影响，那么**根据2.1.1，需要a. 先交换两个prev node的next ； b. 再交换这两个node的next**。无论这两个node的相对位置还是绝对位置，以上的处理总是正确的。
{% endhint %}

> *e.g. Given a linked list, swap every two adjacent nodes and return its head.(*[ *Leetcode: Swap Nodes in Pairs*](https://leetcode.com/problems/swap-nodes-in-pairs/) *)* *Given 1->2->3->4, you should return the list as 2->1->4->3.*

```python
def swapPairs(self, head: ListNode) -> Optional[ListNode]:   
    dummy = ListNode(0)
    dummy.next = head
    
    prev, first = dummy, head
    while first and first.next:
        second = first.next
        prev.next, first.next = first.next, prev.next   # swap prev nodes' next
        first.next, second.next = second.next, first.next   # swap two nodes' next
        prev = first
        first = first.next

    return dummy.next
```

### 2.5 **倒序访问问题**

如果对靠前节点的处理必须在靠后节点之后，即**倒序访问问题**，则可视为**recursion**问题，或可以用`stack`等效解决。

> *e.g. 1 Given input ( 7->1->6 ) + ( 5->9->2 ), output 2->1->9. (* [*LeetCode: add Two Numbers*](https://leetcode.com/problems/add-two-numbers/) *无需递归顺序访问即可，因为靠前计算结果不依赖于靠后节点）*\
> *e.g.2  Given input ( 6->1->7 ) + ( 2->9->5 ), output 9->1->2. (* [*LeetCode: add Two numbers II*](https://leetcode.com/problems/add-two-numbers-ii/) *用递归或stack处理，因为靠前计算结果依赖于后面的计算结果)*