目录
1. 链表的中间结点
给定一个头结点为 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.struct ListNode* middleNode(struct ListNode* head){ struct ListNode* val=head; struct ListNode* valq=head; while(valq!=NULL&&valq->next!=NULL) { valq=valq->next->next; val=val->next; } return val; }
?
解题思路： 通过快慢指针找到中间节点，快指针每次走两步，慢指针每次走一步，当快指针走到结尾的时候，慢指针正好走到中间位置
2. 反转链表?
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]/** * 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* n1,*n2,*n3; n1 = NULL; n2 = head; n3 = n2->next; while(n2) { // 倒指向 n2->next = n1; // 迭代 n1 = n2; n2 = n3; if(n3) n3 = n3->next; } return n1; }// 取节点头插的思想完成逆置 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newhead = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* next = cur->next; //头插新节点，更新头 cur->next = newhead; newhead = cur; cur = next; } return newhead; }
解题思路： 1. 三指针翻转法:? ?记录连续的三个节点，原地修改节点指向
此题一般常用的方法有两种，三指针翻转法和头插法 2. 头插法:??每一个节点都进行头插
?
3. 移除链表元素?
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]?解题方式：哨兵结点的使用有利于链表代码的标准化，可以减少一些额外的分支判断。
解题思路：从头节点开始进行元素删除，每删除一个元素，需要重新链接节点struct ListNode* removeElements(struct ListNode* head, int val) { //dummy哑结点 struct ListNode* dummy = malloc(sizeof(struct ListNode)); dummy->next = head; struct ListNode* cur = dummy; while(cur->next) { if(cur->next->val == val) { struct ListNode* next = cur->next->next; free(cur->next); cur->next = next; } else cur = cur->next; } return dummy->next; }struct ListNode* removeElements(struct ListNode* head, int val) { if(head == NULL) return NULL; struct ListNode* cur = head; struct ListNode* prev = NULL; while(cur) { //如果当前节点是需要删除的节点 if(cur->val == val) { //首先保存下一个节点 struct ListNode* next = cur->next; //如果删除的为头节点，更新头节点 //否则让当前节点的前趋节点链接next节点 if(prev == NULL) { head = cur->next; } else { prev->next = cur->next; } //释放当前节点，让cur指向next free(cur); cur = next; } else { //如果cur不是需要删除的节点，则更新prev,cur prev = cur; cur = cur->next; } } return head; }
?4. 链表分割
描述：
现有一链表的头指针 ListNode*?pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
解题思路 创建两个链表，分别存放小于x的节点和大于等于x的节点，分别进行尾插
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { struct ListNode* lessval,*greatval,*greathead,*lesshead; greathead=greatval=(struct ListNode*)malloc(sizeof(struct ListNode)); lesshead=lessval=(struct ListNode*)malloc(sizeof(struct ListNode)); greatval->next=NULL; lessval->next=NULL; struct ListNode* cur=pHead; while(cur) { if(cur->val<x) { lessval->next=cur; lessval=lessval->next; } else { greatval->next=cur; greatval=greatval->next; } cur=cur->next; } lessval->next=greathead->next; greatval->next=NULL; struct ListNode* head=lesshead->next; free(greathead); free(lesshead); return head; } };
5. 相交链表
题目条件：
给你两个单链表的头节点?headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
解题思路： 此题可以先计算出两个链表的长度，让长的链表先走相差的长度，然后两个链表同时走，直到遇到相同的节点，即为第一个公共节点
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { int lenA=1,lenB=1; struct ListNode* curA=headA; struct ListNode* curB=headB; while(curA) { curA=curA->next; lenA++; } while(curB) { curB=curB->next; lenB++; } int gap=abs(lenA-lenB); if(curA!=curB) { return NULL; } struct ListNode* longlist= headA; struct ListNode* shortlist= headB; if(lenA<lenB) { longlist=headB; shortlist=headA; } //长链表先走gap步 while(gap--) { longlist=longlist->next; } while(longlist!=shortlist) { longlist=longlist->next; shortlist=shortlist->next; } return shortlist; }
6. 环形链表
题目条件：
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递?。仅仅是为了标识链表的实际情况。
如果链表中存在环?，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
解题思路： 定义快慢指针fast,slow, 如果链表确实有环，fast指针一定会在环内追上slow指针
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode Node; bool hasCycle(struct ListNode *head) { Node* slow = head; Node* fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) return true; } return false; }
?
?考虑奇偶情况，如果是奇数那么fast将会指向空造成报错；
7. 环形链表 II?
题目条件：
给定一个链表的头节点 ?head?，返回链表开始入环的第一个节点。?如果链表无环，则返回?null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。解答：slow进环以后，fast在一圈之内，一定追上了slow，追击过程每次缩小一，他们的相对距离最多一圈
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *fast=head; struct ListNode *slow=head; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; if(slow==fast) { struct ListNode *meet=slow; while(meet!=head) { meet=meet->next; head=head->next; } return meet; } } return false; }
证明：为什么快指针每次走两步，慢指针走一步可以？
结论：一定可以追上。
假设：slow与fast距离为N，这时fast真正开始追击slow，fast每次走2步，slow每次走1步，所以每行进一个过程则slow与fast间的距离减一；N->N-1->N-2->...->0，当距离为0时则追上。
证明：快指针一次走3步，走4步，...n步行吗？
假设：fast真正开始追击slow，fast一次走三步，slow一次走1步，他们之间距离每次缩小2。???????
