序言

学习随笔是本人对自己一天的自学回顾，由于本人是非科班出身，不懂很多cs的专业术语，所以难免会有些错误，望各位批评指正，本人定当悉心接受并立即改正。希望自己能够慢慢坚持下去，坚持转行的道路，坚持每天学习的输出。

刷题篇

LeetCode

1.题目

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

2.大致思路

看见链表，找中间结点，第一时间想到 快慢指针，即定义两个指针，快指针移动速度是慢指针移动速度的两倍，当快指针到达尾部，慢指针到达中间。

时间复杂度O(N)。
空间复杂度O(1)。

3.踩坑

题目明明说带有头结点head，结果头结点竟然是第一个元素结点。不知道是我自学有问题还是题目表达又问题。这里还望大佬指正，非常感谢。

4.代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* middleNode(struct ListNode* head){
    if(head->next==NULL) return head;     //若链表只有第一个元素结点，直接返回它
    if(head->next==NULL) return head->next; //若链表有两个元素结点，则返回第二个元素结点
    struct ListNode *p=head,*q=head;
    while(q!=NULL&&q->next!=NULL){
        p=p->next;    //慢指针
        q=q->next->next;   //快指针
    }
    return p;
}

5.解析中的其他思路

1.数组

因为题目附加了一个提示：给定链表的结点数介于 1 和 100 之间，所以可以指定数组长度为100，一边遍历链表，一边存储元素进数组，计数器同时加一。这样可以找到中间元素（即一半）。

可以看出，时间复杂度O(N),空间复杂度O(N).

2.单指针

利用单指针遍历链表，记录链表长度，取一半，再遍历链表至中间元素处。

时间复杂度O(N)，空间复杂度(1)。

1.题目

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

2.大致思路

没看清题目，一开始以为是删除中间的结点，结果用了快慢指针，最后再读题，发现给的是要删除的结点，让我怎么删除它（我吐了）。

这里的删除其实可以“不删除”，利用一些表面现象掩盖掉即可。

如：1,2,3,4 我想删除2，即得到1,3,4 我并不需要真的删除2，我可以用3赋值给2，再让2处的指针指向4即可。

3.代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void deleteNode(struct ListNode* node) {
    struct ListNode *p=node->next;
    *node=*p;
    free(p);
}

4.心得

看清题目还是很有必要的，做题先读题。