203. 移除链表元素
题目
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
题目链接：移除链表元素
解法一：递归
代码如下：
struct ListNode* removeElements(struct ListNode* head, int val){ if(head==NULL) return NULL; head->next=removeElements(head->next,val); return head->val==val?head->next:head; }
递归的写法看起来简洁，实际并没有迭代写法好理解，而且在空间复杂度上也比迭代高，这里的递归写法思路主要是先向下找到尾结点后，向上逐个返回，如果等于val值，就将该节点上一个元素直接指向该节点下一个元素，等于是将该点从链表中删除了
如下图：
解法二：迭代
代码如下：
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* headhead=malloc(sizeof(struct ListNode)); headhead->next=head; struct ListNode* temp=headhead; while(temp->next!=NULL) { if(temp->next->val==val) temp->next=temp->next->next; else temp=temp->next; } return headhead->next; }
迭代的思路就比较好理解了，先创建一个结点空间headhead，让它指向head，再用temp复制该内存地址，使用temp对链表进行遍历，找到等于val值的元素就删除，直至遍历完整个链表，最后headhead指向的下一个位置即为删除val结点的head头结点位置。
206. 反转链表
题目
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
题目链接：反转链表
解法一：递归
代码如下：
struct ListNode* reverseList(struct ListNode* head) { if (head == NULL || head->next == NULL) { return head; } struct ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = NULL; return newHead; }
这里的递归写法相对于上一题更不好理解一些，具体也是向下找到最后一个结点，逐个反转，如下图：
解法二：迭代
代码如下：
struct ListNode* reverseList(struct ListNode* head){ struct ListNode* prev=NULL; struct ListNode* cur=head; while(cur) { struct ListNode* next=cur->next; cur->next=prev; prev=cur; cur=next; } return prev; }
迭代写法就很简单了，设定两个指针，prev指向NULL，cur指向头结点，再用循环从头开始反转，最后prev即为头结点，返回prev即可。
876. 链表的中间结点
题目
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
题目链接：链表的中间结点
解法一：快慢指针法
代码如下：
struct ListNode* middleNode(struct ListNode* head){ struct ListNode* fast = head; struct ListNode* slow = head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; } return slow; }
个人觉得快慢指针的写法更简洁且好理解，大概的思路就是slow指针走一步，fast指针走两步，fast遍历完链表，slow指针指向的即为中间结点。
解法二：单指针法
代码如下:
struct ListNode* middleNode(struct ListNode* head){ int n=0; struct ListNode* cur=head; while(cur!=NULL) { n++; cur=cur->next; } int k=n/2; cur=head; while(k>0) { cur=cur->next; k--; } return cur; }
这个算法的思路就是用cur指针先遍历一遍数组，用n记录结点个数，再用结点数/2的值赋给k，cur重新指向头结点，再进行遍历k个位置，最后cur停在的结点位置即为中间节点位置。
链表中倒数第k个结点
题目
输入一个链表，输出该链表中倒数第k个结点。
题目链接：链表中倒数第k个结点
解法
代码如下：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast=pListHead; struct ListNode* slow=pListHead; while(k--) { if(fast==NULL) { return NULL; } fast=fast->next; } while(fast) { fast=fast->next; slow=slow->next; } return slow; }
这里用的是双指针的写法，先让fast指针向前走k个结点位置，再让fast和slow同时走，直到fast走到NULL，此时的slow指向的就是倒数第k个结点。
21. 合并两个有序链表
题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
题目链接：合并两个有序链表
解法一：递归
代码如下：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ if(list1==NULL) return list2; else if(list2==NULL) return list1; else if(list1->val<list2->val) { list1->next=mergeTwoLists(list1->next,list2); return list1; } else { list2->next=mergeTwoLists(list1,list2->next); return list2; } }
这种递归写法相对好理解一些，前两个条件是考虑list1或list2为空的情况发生，后两个条件都是使用递归，当list1头结点值小于list2头结点值时，则头结点为list1，否则为list2，然后继续向下一结点递归，最后合并完整个链表。
解法二：迭代
代码如下：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode* list3=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* p3=list3; while(list1!=NULL&&list2!=NULL) { if(list1->val<list2->val) { p3->next=list1; list1=list1->next; p3=p3->next; p3->next=NULL; } else { p3->next=list2; list2=list2->next; p3=p3->next; p3->next=NULL; } } if(list1==NULL) p3->next=list2; if(list2==NULL) p3->next=list1; return list3->next; }
这种写法的思路是借助额外的空间，也是逐个比较大小，再将结点从小到大串联，最后返回额外的空间结点指向的下一结点，即为调整好的链表。
