前言

链表是一个不常使用在日常软件开发中的数据结构，但是，却经常会被用于出算法题，这是因为，链表的两个元素之间是通过next指针相连，如果没有维护好这个指针信息，就会导致无法访问到某一元素。

我们一般使用单向链表，其中每个元素的结构包括一个data变量和一个next指针，前者用于存储数据，后者用于记录下一个元素的地址，C语言的表示为：

typedef struct LinkedListNode {
    int data;
    struct LinkedListNode* next;
} LLN;

简单的例子：反转链表

这道题可以通过LeetCode 206访问，这道题的一个AC解是：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    struct ListNode* neno = head->next;
    while(curr != NULL) {
        //neno = curr->next;
        curr->next = prev;
        prev = curr;
        curr = neno;
        neno  = (neno == NULL) ? NULL : neno->next;
    }
    return prev;
}

在循环内，neno的赋值选择注释掉的一行还是未注释的一行都可以。只涉及$O(1)$空间复杂度的链表反转，重要之处在于如何维护next节点的信息。因为，当反转链表时，由于next指向的问题，如果不维护下一个节点的信息，那么下一次迭代就没有办法访问了。

所以这道题的逻辑是这样的：

1. 下一个节点的维护：记录当前节点的下一个节点。
2. 主要逻辑：反转当前节点的下一节点指向。
3. 为下一次迭代做准备：即prev和curr节点的赋值。

只要是涉及链表的算法，最重要的就是如何维护下一个节点的信息。

简单的例子：合并两个排好序的链表

这道题可以通过LeetCode 21访问，这道题的一个AC解是：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 0;
    head->next = NULL;
    struct ListNode* curr = head;
    struct ListNode* p1 = list1;
    struct ListNode* p2 = list2;
    while(p1 != NULL || p2 != NULL) {
        if(p2 == NULL) {
            curr->next = p1;
            p1 = p1->next;
        } else if(p1 == NULL) {
            curr->next = p2;
            p2 = p2->next;
        } else {
            if(p1->val >= p2->val) {
                curr->next = p2;
                p2 = p2->next;
            } else {
                curr->next = p1;
                p1 = p1->next;
            }
        }
        curr = curr->next;
    }
    return head->next;
}

值得注意的是，我不推荐任何人使用C去进行LeetCode的作答，比如malloc后的赋值操作，对于算法没有任何影响，但是删除这两句，便无法AC。

这道题就很好体现了我们之前说的三个步骤：

1. 下一个节点的维护：划分不同条件，根据空指针、值大小判断当前节点接续什么节点。
2. 主要逻辑：接续的过程。
3. 为下一次迭代做准备：将curr节点变作它的下一个节点。

中等的例子：快慢指针

这道题可以通过LeetCode 141访问，一个AC解是：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr) {
            return false;
        }
        ListNode* slowp = head, *fastp = head->next;
        while(slowp != fastp) {
            if(fastp == nullptr || fastp->next == nullptr) {
                return false;
            }
            slowp = slowp->next;
            fastp = fastp->next->next;
        }
        return true;
    }
};

这道题的关键在于，一个链表如果有环，那么迭代将永远无法遇到空指针，并且利用不同速度迭代，将会相遇。那么，我们可以让一个指针走得快一些，一个指针慢一些，如果遇到了空指针，就是无环，如果相遇了就是有环。

这道题同样是三个步骤：

1. 下一个节点的维护：确定快慢指针的落点。
2. 主要逻辑：是否遇到空指针？是否快慢指针相遇？
3. 为下一次迭代做准备。

中等的例子：链表的重排

这道题可以通过LeetCode 143访问，一个AC解是：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode* curr = head;
        vector<ListNode*> v;
        while(curr != nullptr) {
            v.push_back(curr);
            curr = curr->next;
        }
        curr = head;
        for(int i = 0; i < v.size() / 2; ++i) {
            if(i != 0) {
                curr->next = v[i];
                curr = curr->next;
            }
            curr->next = v[v.size() - i - 1];
            curr = curr->next;
        }
        if(v.size() % 2 == 1) {
            curr->next = v[v.size() / 2];
            curr = curr->next;
        }
        curr->next = nullptr;
    }
};

这道题的重要之处在于后续节点的处理，尤其是最后一行——最后一个节点的next节点要清空。其实这道题本身不难，只是最后一行的curr->next=nullptr;如果没有想到，会花掉大量的调试时间。

中等的例子：深度拷贝链表

这道题可以通过LeetCode 138访问，一个AC解是：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> um;
        Node* curr = head;
        while(curr != nullptr) {
            Node* copy = (Node*)malloc(sizeof(Node));
            copy->val = curr->val;
            copy->next = nullptr;
            copy->random = nullptr;

            um.insert({curr, copy});
            curr = curr->next;
        }
        curr = head;
        while(curr != nullptr) {
            um[curr]->next = um[curr->next];
            um[curr]->random = um[curr->random];
            curr = curr->next;
        }
        return um[head];
    }
};

这道题的重要之处在于，通过一种连接索引关系，恢复另一种索引关系。先根据next深度拷贝每个节点，然后根据next节点的索引关系恢复random节点。