✈移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
方法一：
遍历链表找到所有等于val的节点，再执行删除操作删除这些节点。
方法二：
双指针
创建两个指针，一个在前，一个在后。
如果前面的指针指向的元素等于val，将后面的指针连上前面指针的下一个指针，前面的指针向前走一格；
如果前面的指针指向的元素不等于val，那么两个指针都向前走一格。
再处理一些特殊情况：
struct ListNode* removeElements(struct ListNode* head, int val) {
ListNode * last = head;
ListNode* tmp = head;
if (last == NULL || (last->next == NULL && last->val == val))//如果是空链表或只有一个val的链表
{
return NULL;
}
else if (last->next == NULL)//如果只有一个节点且不等于val的链表
{
return head;
}
else
{
while (tmp != NULL)
{
if (tmp == last)
{
tmp = tmp->next;
}
if (tmp->val==val)
{
last->next = tmp->next;
tmp = tmp->next;
}
else
{
last = last->next;
tmp = tmp->next;
}
}
if (head->val == val)//如果第一个节点的元素就等于val
{
return head->next;
}
last->next = NULL;
}
return head;
}原题链接：
✈反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
双指针法：
创建两个指针，一个在前，一个在后。
每次循环，将前面的指针指向的链表指向在后面的指针，后面的指针赋值成前一个，前一个往下走一格。
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL || head->next == NULL)//如果只有一个或者没有节点
{
return head;
}
ListNode* pre = head->next;
head->next = NULL;
while (pre != NULL)
{
ListNode* tmp = pre->next;
pre->next = head;
head = pre;
pre = tmp;
}
return head;
}原题链接：
✈合并两个有序链表
双指针法：
创建三个指针，一个指向第一个链表，一个指向第二个链表，一个指向新链表的末尾。
如果第一个指针指向的元素比第二个指针小，那么就让新链表的末尾指向第一个指针，第一个指针再向后移一格，第三个指针向后移一格；
如果第二个指针指向的元素比第一个指针小，那么就让新链表的末尾指向第二个指针，第二个指针再向后移一格，第三个指针向后移一格。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if (list1 == NULL)//先解决其中存在空链表的情况
{
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else
{
ListNode* pre = NULL;
ListNode* finnal = NULL;
if (list1->val <= list2->val)//初始化pre，确定新链表的的头节点finnal
{
finnal = list1;
pre = list1;
list1 = list1->next;
}
else
{
finnal = list2;
pre = list2;
list2 = list2->next;
}
while (list1 != NULL && list2 != NULL)//取元素到新的链表中
{
if (list1->val <= list2->val)
{
pre->next = list1;
pre = list1;
list1 = list1->next;
}
else
{
pre->next = list2;
pre = list2;
list2 = list2->next;
}
}
if (list1 == NULL)
{
pre->next = list2;
}
else
{
pre->next = list1;
}
return finnal;
}
}原题链接：
✈链表的中间节点
快慢指针法：
创建两个指针，一个快指针，一个慢指针，两个指针初始值为链表的起点。快指针每次走两格，慢指针每次走一格。
如果链表中有奇数个节点，当快指针的下一个节点为NULL时，慢指针走到中间节点的位置；
如果链表中有偶数个节点，当快指针为NULL时，慢指针走到中间节点的位置。
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (1)
{
if (fast == NULL || fast->next == NULL)
{
return slow;
}
fast = fast->next;
fast = fast->next;
slow = slow->next;
}
}原题链接：
✈环形链表的约瑟夫问题
环形链表法：
创建一个n个节点的环形链表，并且第n个节点的存储的元素是n。
删去第m个的值，并且循环n-1次。
typedef struct ListNode {
int val;
struct ListNode* next;
}ListNode;
int ysf(int n, int m) {
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
assert(head);
head->val = 1;
head->next = head;
ListNode* pre = head;
for (int i = 2; i <=n; i++)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->next = head;
newnode->val = i;
pre->next = newnode;
pre = newnode;
}
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < m-1; j++)
{
pre = pre->next;
}
pre->next = pre->next->next;
}
return pre->val;
}原题链接：
