链表 - acgtyrant/Algorithm-and-Data-Structure GitHub Wiki
递归反转除去首元素之外的子链表，再通过接着 head->next->next = head, head->next = NULL 即可。别忘了用递归函数不停地返回链表的尾元素，毕竟 test 函数需要一个代表头节点的 struct ListNode *, 除了在 reverseList 的返回值接收，别无他法。
/**
* 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 *tail = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return tail;
}当链表长度不大于一时，直接返回，否则就特殊处理 head, 让它指向 NULL, 且后续 node 指向 head. 接着剩下的工作便是精心构造三个迭代器、循环中依次反转掉是了，别忘了用迭代器返回指向新头节点的链接：
/**
* 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 *iterator = head;
struct ListNode *temporary_iterator = iterator->next;
struct ListNode *iterator_next = temporary_iterator->next;
head->next = NULL;
temporary_iterator->next = iterator;
while (iterator_next != NULL) {
iterator = temporary_iterator;
temporary_iterator = iterator_next;
iterator_next = temporary_iterator->next;
temporary_iterator->next = iterator;
}
return temporary_iterator;
}首选考虑首元素以及后续元素全是 val 的极端情况，要么迭代到尾后 node 即 NULL, 要么迭代到第一个此 val 非彼 val 的 left_node. 接着继续迭代，要么迭代到尾后 node 即 NULL, 要么迭代到第一个等于 val 的 node, 接着定义它的下一个 right_node, 以继续迭代到第一个不等于 val 的 node, 这时 (left_node, right_node) 正好是一个值域逼近 val 的区间，直接 left_node->next = right_node. 最后再 left_node = right_node, 如此循环反复。
说实话这函数过程需要・精・心・无・比・地・设・计，以致我怀疑难度至少应该为 Medium:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val) {
while (head != NULL && head->val == val) head = head->next;
struct ListNode *left_node = head;
struct ListNode *right_node;
while (left_node != NULL) {
while (left_node->next != NULL && left_node->next->val != val) {
left_node = left_node->next;
}
if (left_node->next == NULL) return head;
right_node = left_node->next->next;
while (right_node != NULL && right_node->val == val) {
right_node = right_node->next;
}
left_node->next = right_node;
left_node = right_node;
}
return head;
}然而有 10% 的Ｃ实现比我的还要好，我花了 12 ms, 他们花了 8ms. 去讨论区看了下，发现其实只要创建一个虚拟头节点 dummy 且 dummy->next = head 就可以了，也不怕 head 为 NULL 或头几个 node 全等于 val 的极端情况：
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
dummy->next = head;
struct ListNode *p = dummy;
while (p->next != NULL) {
if (p->next->val == val) {
p->next = p->next->next;
} else {
p = p->next;
}
}
head = dummy->next;
free(dummy);
return head;
}别忘了重置 head, 并 free 掉 dummy.
然而实际耗时依然是 12ms! 试了讨论区中其它号称 8ms 的代码，一样，我估计是因为官方测试用编译器的版本已经不一致了。
Remove Duplicates from Sorted List
没看清题目，不知道 linked list 是 sorted 的，白构造一个 vector 数组用于储存独一无二的值，白写 IsItDuplicate 函数：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
bool IsItDuplicate(int val, vector<int> vals) {
for (auto unique_val : vals) {
if (val == unique_val) return true;
}
return false;
}
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
vector<int> vals;
ListNode *dummy = new ListNode(0);
ListNode *p = dummy;
p->next = head;
while (p->next != NULL) {
if (IsItDuplicate(p->next->val, vals)) {
p->next = p->next->next;
} else {
vals.push_back(p->next->val);
p = p->next;
}
}
delete dummy;
return head;
}
};当然这不妨碍它 accpeted, 虽然性能排名非常落后。
重写为Ｃ实现, dummy 大法好！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplicates(struct ListNode* head) {
struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode *p = dummy;
p->next = head;
while (p->next != NULL && p->next->next != NULL) {
if (p->next->val == p->next->next->val) {
p->next = p->next->next;
} else {
p = p->next;
}
}
head = dummy->next;
free(dummy);
return head;
}当初一看题目，很奇怪，deleteNode 的形参就一个，怎么知道要删除的节点是哪一个？查了下，才发现题目原来如同字面上的意思，形参指向的不是头节点，而是所要删除的节点且该题有解。
题目说了 node 不会是尾节点，我们可以放心地这样写：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
void deleteNode(struct ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}这算是我目前碰到过最简单的题目了。
在做这题前，友情提醒下：这题翻译成人话，就是「给定一个列表，连续把列表向右翻转到左边 k 次，k 非零。比如，给定 1->2->3->4->5->NULL 和 k = 2, 那么返回 4->5->1->2->3->NULL.」。注意这题目上有不少非常隐蔽的描述性假设，从而是陷阱噢。
遍历两次链表，第一次计算 size, 第二次找出翻转所要打断的关键结点，然而旧链接该删的删、新链接该加的加即可。然而陷阱多多，k 可以是零，也可以大于 size! 对于后者，我们得取模，这该死的英文文字游戏。然而我取模时又中了当 size 为零的运行时陷阱，好坑啊。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* rotateRight(struct ListNode* head, int k) {
if (head == NULL || k == 0) return head;
struct ListNode *dummy_head = (struct ListNode *)malloc(sizeof(struct ListNode));
dummy_head->next = head;
int numbers = 0;
struct ListNode *index = dummy_head;
while (index->next != NULL) {
index = index->next;
++numbers;
}
k %= numbers;
if (k == 0) return head;
struct ListNode *end = index;
index = dummy_head;
while (numbers != k) {
index = index->next;
--numbers;
}
dummy_head->next = index->next;
end->next = head;
index->next = NULL;
head = dummy_head->next;
free(dummy_head);
return head;
}