一、移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
输入：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
输出：[ ]
链接:https://leetcode-cn.com/problems/remove-linked-list-elements
思路动图： 利用双指针法，先找到要删除的节点并保存前一个结点的位置
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* prev= NULL; struct ListNode* next = head; while(next != NULL) { //不相等，向后找 if(next->val != val) { prev = next; next = next->next; } //找到了 else { //如果节点元素全部相等的情况 if(next == head) { head = next->next; free(next); next = head; } //不相等，先链接到要删除节点的下一个结点，在释放 else { prev->next = next->next; free(next); next = prev->next; } } } return head; }
二、反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
链接：https://leetcode-cn.com/problems/reverse-linked-list/
思路动图： 三指针法
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ //链表为空 if(head == NULL) return NULL; //创建三个指针 struct ListNode* cur,*prev,*next; cur = NULL; prev = head; next = head->next; while(prev) { prev->next = cur; cur = prev; prev = next; if(next) next = next->next; } return cur; }
三、链表的中间结点
给定一个头结点为 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，我们返回第二个结点。
链接：https://leetcode-cn.com/problems/middle-of-the-linked-list
思路： 快慢指针法
快、慢指针同时从头结点出发，慢指针一次走一个节点，快指针一次走两个节点；此时会有两种情况：
情况1：
情况2：
思路动图：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head){ struct ListNode* slow,* fast; slow = fast = head; while(fast && fast -> next) { fast = fast -> next -> next; slow = slow -> next; } return slow; }
四、链表中倒数第k个结点
这是牛客网的一道题
输入一个链表，输出倒数第k个结点
示例：
输入：1, { 1, 2, 3, 4, 5 }
返回值：{ 5 }
思路： 快慢指针法
我们要找到倒数第 k 个结点，以 k = 3 为例，我们只要保证快指针与慢指针之间相差两步，直到快指针走到尾结点，返回慢指针，此时就是倒数第 k 个结点；
从上图可以看出只要保证两步之遥，当fast指针走到空时，slow指针就是倒数第k个指针，所以无论k是多少只要两指针间距为k-1即可；
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* slow, *fast; slow = fast = pListHead; while(k--) { if(fast == NULL) { return NULL; } fast = fast -> next; } while(fast) { slow = slow -> next; fast = fast -> next; } return slow; }
五、合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的 ；
输入：l1 = [ 1, 2, 4 ], l2 = [ 1, 3, 4 ]
输出：[ 1, 1, 2, 3, 4, 4]
示例 2：
输入：l1 = [ ], l2 = [ ]
输出：[ ]
示例 3：
输入：l1 = [ ], l2 = [ 0 ]
输出：[ 0 ]
提示：
两个链表的节点数目范围是 [ 0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
思路动图：
两个链表进行比较，谁小就拿谁，组成新的链表；
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //任何一个链表为空，就返回另外一个 if(list1 == NULL) return list2; if(list2 == NULL) return list1; //创建两个节点，用来存储新链表 struct ListNode* head = NULL; struct ListNode* tail = NULL; head = tail =(struct ListNode*)malloc(sizeof(struct ListNode)); while(list1 && list2) { if(list1->val > list2->val) { //取list2 tail->next = list2; tail = list2; list2 = list2->next; } else { //取list1 tail->next = list1; tail = list1; list1 = list1->next; } } //循环结束，会存在一个链表没走完的情况 if(list1) tail->next = list1; if(list2) tail->next = list2; struct ListNode* newlist = head->next; free(head); return newlist; }
