【算法学习之路】7.链表算法

前言

我会将一些常用的算法以及对应的题单给写完，形成一套完整的算法体系，以及大量的各个难度的题目，目前算法也写了几篇，题单正在更新，其他的也会陆陆续续的更新，希望大家点赞收藏我会尽快更新的！！！

一.原地逆置

思路一：头插法

若带头节点，先将头节点摘下来
然后从第一个节点开始，挨个插入每一个节点
摘下来后用头插法建立新的链表

思路二：双指针法

定义两个指针pre和cur，pre在前cur在后
每次让pre的next指向cur，实现一次局部反转
局部反转之后。pre和cur同时往后移动一个位置，循环上述过程，直至pre到达链表尾部（在循环过程中需要记录pre->next）

思路3：递归

递归出口：传进来的节点p的next = NULL
递归体：递归调用，把p之后的先反转

例题：

力扣206. 反转链表

1.头插法

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///头插法
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* p = head;if(head == NULL){//先判断是否为空return NULL;}struct ListNode* q = p->next;head = NULL;//将节点从链表拿下来while(q != NULL){p->next = head;head = p;p = q;q = q->next;}p->next = head;return p;
}

2.双指针法

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///双指针法
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* p = head;//指向头节点struct ListNode* q = NULL;//指向头节点的上一个节点while(p != NULL){//struct ListNode* t = p->next;//保存p->nextp->next = q;q = p;p = t;}return q;
}

3，递归

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///递归
struct ListNode* reverse (struct ListNode* cur, struct ListNode* pre);struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head;struct ListNode* pre = NULL;return reverse (cur, pre);
}struct ListNode* reverse (struct ListNode* cur, struct ListNode* pre){if (cur == NULL) {return pre;}else {struct ListNode* tmp = cur -> next;cur -> next = pre;return reverse (tmp, cur);}
}

二.双指针

快慢指针：一个指针快一个指针慢

例题1

力扣LCR 140. 训练计划 II

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* trainingPlan(struct ListNode* head, int cnt) {struct ListNode* cur = head;struct ListNode* next = head;for(int i = 0; i < cnt; i++){next = next->next;}while(next){cur = cur->next;next = next->next;}return cur;
}

例题2

力扣142. 环形链表 II

找环开始节点慢指针每次走一个节点，快指针每次走两个节点，当相遇时，再来一个指针从头一个一个走。当与慢指针相遇的时候为开始节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {if(head == NULL || head->next == NULL || head->next->next == NULL){return NULL;}struct ListNode* s = head;struct ListNode* f = head;while(f != NULL){s = s->next;if(f->next == NULL){return NULL;}f = f->next->next;if(f == s){struct ListNode* t = head;while(t != s){t = t->next;s = s->next;}return t;}}return NULL;}

未完待续……