# 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.* \
> \&#xNAN;*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/)\
> \&#xNAN;*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处理，因为靠前计算结果依赖于后面的计算结果)*


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://smilence-yu.gitbook.io/coding/chapter-2-linked-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.