链表这种数据结构的考察实在是太常见了，从大一的c语言课程设计就已经接触到了，作为一种动态的数据结构，它实在是有太多的应用了。话不多说，直接看题。

剑指Offer24

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

思路：链表中最为经典的反转链表。在我看到这个题的第一眼想到的方法就是直接模拟反转过程，多申请一个链表来储存已经反转的节点的next即可，在写完这个方法之后，又想到了更加直接的方法，就是利用递归到尾节点，从尾节点开始反转，总的来说，万物皆可递归。

//模拟
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL){
            return head;
        }
        ListNode * tail, *newHead = NULL;
        tail = head;
        while(tail != nullptr){
            ListNode *pre = tail->next;
            tail->next = newHead;
            newHead = tail;
            tail = pre;
        }
        return newHead;
    }
};

//递归
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode * res = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return res;
    }
};

剑指Offer22

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

思路：首先我们最直观的思路就是直接遍历一遍链表获取链表长度，然后再次遍历输出倒数第k个节点即可，这样需要遍历两遍。然后我们可以思考怎么只让它遍历一遍就能得到答案，倒数第k个节点其实就是第n-k个节点，我们只要确保一个节点从头节点走n-k步就好了，我们就可以创建两个指针，让一个指针先走k步，然后两个指针一起走，后面这个指针就只走了n-k步了。

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(head == NULL || k == 0){
            return head;
        }
        ListNode *pre = head;
        for(int i = 0; i < k; i++){
            if(pre != NULL){
                pre = pre->next;
            }else{
                return NULL;
            }
        }
        while(pre != NULL){
            pre = pre->next;
            head = head->next; 
        }
        return head;
    }
};

剑指Offer52

输入两个链表，找出它们的第一个公共节点。

思路：分别设两个链表的长度为a和b，设公共部分长度为c。一个指针指向A，一个指针指向B，指针A遍历完A之后指向B的头节点遍历至第一个相交的距离为a+b-c，指针B遍历完B之后指向A的头节点遍历至交点的距离为b+a-c，两者的长度相等，此时只有两种情况：

若A和B有交点，此时的位置为第一个公共节点

若A和B没有交点，此时的位置皆为NULL。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *a = headA, *b = headB;
        while(a != b){
            a = a != NULL? a->next : headB;
            b = b != NULL? b->next : headA;
        }
        return a;
    }
};

剑指Offer06

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）

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

思路：看到遍历链表的第一个思路就是递归，直接递归到尾节点，一个个的存进去即可。

class Solution {
public:
    vector<int> res;
    vector<int> reversePrint(ListNode* head) {
        dp(head);
        return res;
    }
private:
    void dp(ListNode* head){
        if(head == NULL){
            return;
        }
        dp(head->next);
        res.push_back(head->val);
    }
};

剑指Offer18

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

思路：这个问题较为简单，由于链表不能走回头路，我们就需要通过node->next->val来判断是不是需要删除的节点即可。

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head->val == val){
                return head->next;
            }
        ListNode * tail = head;
        while(tail->next !=nullptr){
            if(tail->next->val == val){
                tail->next = tail->next->next;
                return head;
            }
            tail = tail->next;
        }
        tail->next = nullptr;
        return head;
    }
};

后记

上周写了个需求，看了下深入理解计算机系统，感觉cs的世界真的宏大，还得加油学习！！！