1. 删除链表中等于val 的所有节点
203. 移除链表元素
难度简单
给你一个链表的头节点 head 和一个整数 val ，
请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
提示：
- 列表中的节点数目在范围 [0, 10^4] 内
- 1 <= Node.val <= 50
- 0 <= val <= 50
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { }
代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur = head; struct ListNode* prev = NULL; while (cur) { if (cur->val == val) { if (cur == head) { head = cur->next; free(cur); cur = head; } else { prev->next = cur->next; free(cur); cur = prev->next; } } else { prev = cur; cur = cur->next; } } return head; }
2. 反转一个单链表
206. 反转链表
难度简单
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目范围是 [0, 5000]
- -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { }
时间O(N^2)的代码：
（自己第一遍写的笨方法）过了挺高兴，看完别人的思路就...
struct ListNode* reverseList(struct ListNode* head) { if (head == NULL) { return NULL; } struct ListNode* cur = head; while (cur->next)//直接找到最后一个在指回来 { cur = cur->next; } struct ListNode* newHead = cur; while(cur!=head) { struct ListNode* prev = head; while (prev->next != cur) { prev = prev->next; } cur->next = prev; cur = prev; } cur->next = NULL; return newHead; }
时间O(N)的代码（三指针）：
struct ListNode* reverseList(struct ListNode* head) { if(head==NULL) { return NULL; } struct ListNode *n1=NULL,*n2=head,*n3=head->next; while(n2) { n2->next=n1;//翻转 n1=n2;//迭代往后走 n2=n3; if(n3!=NULL) { n3=n3->next; } } return n1; }
简化：
struct ListNode* reverseList(struct ListNode* head) { struct ListNode *n1=NULL,*n2=head; while(n2) { struct ListNode *n3=n2->next; n2->next=n1;//翻转 n1=n2;//迭代往后走 n2=n3; } return n1; }
时间O(N)的代码（头插）：
其实和上面本源是一样的（上面简化后应该就是这个了），只是名字变了可能更好理解
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newHead=NULL,*cur=head; while(cur) { struct ListNode* curNext=cur->next; cur->next=newHead;//头插 newHead=cur;//迭代往后走 cur=curNext; } return newHead; }
3.返回链表的中间结点
876. 链表的中间结点
难度简单
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
- 给定链表的结点数介于 1 和 100 之间。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head){ }
数据结构与算法⑤(第二章OJ题，上)前五道链表面试题（下）：https://developer.aliyun.com/article/1513350
