题目难度依次递增
移除链表元素
题目链接：LeetCode203.移除链表元素
题目：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
提示：
- 列表中的节点数目在范围 [0, 104] 内
- 1 <= Node.val <= 50
- 0 <= val <= 50
题解： 方法一
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* prev = NULL;
struct ListNode* cur = head;//把头指针赋给cur
while (cur)//查找链表结束条件
{
if (cur->val != val)
{
prev = cur;//标记cur的前一个指针
cur = cur->next;//让cur指向下一个结点
}
else
{
struct ListNode* next = cur->next;//定义cur结点的下一个位置
if (prev == NULL)//头结点就是val的情况
{
free(cur);//释放当前结点
head = next;//让头指针指向下一个结点
cur = next;//让cur指向下一个结点
}
else
{
free(cur);//释放cur结点
prev->next = next;//让prev指向cur的下一个结点
cur = next;//让cur指向下一个结点
}
}
}
return head;//返回头指针地址
}
方法二：
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode*cur=head;
struct ListNode*prev=NULL;
while(cur)
{
if(cur->val!=val)
{
prev=cur;
cur=cur->next;
}
else
{
if(prev==NULL)
{
head=cur->next;
free(cur);
cur=head;
}
else
{
prev->next=cur->next;
free(cur);
cur=prev->next;
}
}
}
return head;
}
反转链表
题目链接： LeetCode206.反转链表
题目：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
题目分析：
题解： 方法一
struct ListNode* reverseList(struct ListNode* head)
{
if (head == NULL)//链表为空的情况
return NULL;
struct ListNode* n1, * n2, * n3;
n1 = NULL;
n2 = head;
n3 = n2->next;//n3指向n2的下一个结点
while (n2)
{
n2->next = n1;//让n2这个结点指向n1
n1 = n2;
n2 = n3;
if (n3)//如果n3为空，则程序会崩溃，所以判断一下
n3 = n3->next;
}
return n1;//返回反转链表后的头结点
}
方法二：
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
while (cur)//cur不为NULL时执行循环
{
struct ListNode* next = cur->next;
//头插
cur->next = newhead;//让cur指向新的头结点
newhead = cur;//更新newhead
cur = next;//让cur继续向后走
}
return newhead;//返回新的头结点
}
链表的中间结点
题目链接： LeetCode876.链表的中间结点
题目：
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
提示： 给定链表的结点数介于 1 和 100 之间。
题目分析：
我们定义两个指针，slow和fast。slow每次走一步，fast每次走两步。
题解：
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode*slow,*fast;
slow=fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
思考： 上诉代码中 while(fast&&fast->next) 可不可以写为：while(fast->next&&fast)?
注意： 我们是不可以将while中的条件调换的，如果我们将while中的条件调换，那么当链表中结点为偶数的时候，结束时fast已经为空了，我们不能用空指针来访问next，这样做代码就会崩溃。我们应该采用第一种写法（while(fast&&fast->next)），当fast为空时便不会在判断后面的条件，而是直接跳出循环。
链表中倒数第K个结点
题目链接： 牛客网：链表中倒数第K个结点
题目：
输入一个链表，输出该链表中倒数第k个结点。
题目分析：
我们先定义两个指针，fast和slow。
1.fast先走K步。
2.slow和fast同时走，fast走到尾时，slow就是倒数第K个。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
struct ListNode* slow, * fast;
slow = fast = pListHead;
//fast先走K步
while (k--)
{
if (fast == NULL)//如果链表为空了，就提前结束
return NULL;
fast = fast->next;
}
while (fast)
{
fast = fast->next;
slow = slow->next;
}
return slow;//返回倒数第K个结点的地址
}
合并两个有序链表
题目链接： LeetCode21.合并两个有序链表
题目：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
提示：
- 两个链表的节点数目范围是 [0, 50]
- -100 <= Node.val <= 100
- 11 和 12 均按 非递减顺序 排列
题目分析： 我们依次取出两个链表中较小的去尾插，当一个链表为空时，将另一个链表链接在目标链表的尾部。
题解： 方法一：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
//若有链表为空的情况
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
struct ListNode* tail, * head;
tail = head = NULL;
while (list1 && list2)//如果list1和list2都不为空就进入循环
{
if (list1->val < list2->val)
{
if (head == NULL)//头结点为空的情况
{
tail = head = list1;
}
else
{
tail->next = list1;
tail = list1;
}
list1 = list1->next;
}
else
{
if (head == NULL)
{
tail = head = list2;
}
else
{
tail->next = list2;
tail = list2;
}
list2 = list2->next;
}
}
//循环结束后，将另外一个没有走完的链表直接链接在目标链表的后面
if (list1 == NULL)
tail->next = list2;
if (list2 == NULL)
tail->next = list1;
return head;//返回目标链表头结点的地址
}
方法二：定义一个带哨兵位的头结点
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode* head = NULL, * tail = NULL;
//带哨兵位的
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));//定义一个哨兵位头结点
head->next = NULL;//让哨兵位指向空
while (list1 && list2)
{
if (list1->val < list2->val)
{
tail->next = list1;
tail = list1;
list1 = list1->next;
}
else
{
tail->next = list2;
tail = list2;
list2 = list2->next;
}
}
if (list1 == NULL)
tail->next = list2;
if (list2 == NULL)
tail->next = list1;
struct ListNode* list = head->next;
free(head);//释放申请的哨兵位头结点
return list;
}
链表分割
题目链接： CM11 链表分割
题目：
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
题目分析：
遍历原链表。把 <X 的插入到链表1，把 >X 的插入到链表2。 链表1和链表2链接起来。
题解：
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* LessHead, * LessTail, * GreaterHead, * GreaterTail;
LessHead = LessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
GreaterHead = GreaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
LessHead->next = GreaterHead->next = NULL;//让哨兵位的头结点指向空
struct ListNode* cur = pHead;
while (cur)//判断链表是否遍历结束
{
if (cur->val < x)
{
LessTail->next = cur;
LessTail = LessTail->next;
}
else
{
GreaterTail->next = cur;
GreaterTail = GreaterTail->next;
}
cur = cur->next;
}
LessTail->next = GreaterHead->next;//将GreaterHead链接到LessTail上面
GreaterTail->next = NULL;//让目标链表的尾结点指向空，避免最后一个结点存着链表中某一个结点的地址，从而指向那个结点造成链表的部分循环。
struct ListNode* list = LessHead->next;//定义list指向目标链表的头结点
free(LessHead);//释放申请的哨兵位结点
free(GreaterHead);//释放申请的哨兵位结点
return list;//返回目标链表的头结点
}
};
链表的回文结构
题目链接： OR36 链表的回文结构
题目：
对于一个链表，请设计一个时间复杂度为O(n),额外**空间复杂度为O(1)**的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：1->2->2->1
返回：true
题目分析：
题解：
class PalindromeList {
public:
//反转链表，然会返回目标链表的头结点
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
while (cur)//cur不为NULL时执行循环
{
struct ListNode* next = cur->next;
//头插
cur->next = newhead;//让cur指向新的头结点
newhead = cur;//更新newhead
cur = next;//让cur继续向后走
}
return newhead;//返回新的头结点
}
//找到链表的中间结点并返回地址
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow, * fast;
slow = fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
bool chkPalindrome(struct ListNode* A)
{
struct ListNode* mid = middleNode(A);//找到A链表的中间结点
struct ListNode* rHead = reverseList(mid);//反转mid之后的链表
while (A && rHead)//其中一个链表走完循环就结束
{
if (A->val == rHead->val)
{
A = A->next;
rHead = rHead->next;
}
else
return false;
}
return true;
}
};
链表相交
题目链接： LeetCode160.相交链表
题目：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
题目分析：
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
struct ListNode* tailA = headA, * tailB = headB;
int lenA = 1, lenB = 1;//让最开始的lenA和lenB的值为1，否则计算的链表长度会比实际长度小1
while (tailA->next)
{
tailA = tailA->next;
++lenA;//计算A链表的长度
}
while (tailB->next)
{
tailB = tailB->next;
++lenB;//计算B链表的长度
}
if (tailA != tailB)//如果两个链表的尾结点不相等，那么链表就不相交
return NULL;
//链表相交，求交点。长的链表先走差距步，再同时走找交点。
struct ListNode* shortList = headA, * longList = headB;//定义的时候默认A链表为短链表
if (lenA > lenB)//如果A链表比较长，就小调整一下
{
longList = headA;
shortList = headB;
}
int gap = abs(lenA - lenB);//链表A与链表B的长度差
while (gap--)//让较长的链表先走差距步
{
longList = longList->next;
}
while (shortList && longList)//A链表和B链表都不为空，则进入循环
{
if (shortList == longList)
return shortList;//返回两个链表的交点
shortList = shortList->next;
longList = longList->next;
}
return NULL;//编译器检查语法的时候，必须在这里有返回值，否则就会出现语法错误。尽管代码的逻辑执行并没有错。
}
注意：
这里我们需要特别注意一点，在代码末尾一行的时候，我们必须写上返回值，即使这个代码不会执行到这一行。因为编译器对代码进行语法检查的时候，它并不会去看你执行代码的逻辑是否正确，而是看你的语法是否有误，如果不写这一行，编译器就会认为没有返回值而报出语法错误。
环形链表
题目链接：LeetCode141.环形链表
题目：
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
题目分析：
思路：快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。
问：在带环链表中，为什么快指针每次走两步，慢指针走一步就一定会追上？
证明如下：
问题扩展：
slow一次走1步，fast一次走3步，能追上吗？fast一次走4步呢？n步呢？
结论：因为链表的长度是不一定的，所以在带环链表中，若想要slow（慢指针）能够追上fast（快指针），只能够让slow每次走一步，fast每次走两步，这样就一定会追上。如果slow每次走一步，fast走两步以上，那么将不一定会追上。
题解：
bool hasCycle(struct ListNode* head)
{
struct ListNode* slow, * fast;
slow = fast = head;//slow和fast同时指向头结点
while (fast && fast->next)//链表结点可能为奇数也可能为偶数，所以需要这样判断。但判断的条件顺序不能够颠倒。
{
fast = fast->next->next;//fast向后走两步
slow = slow->next;//slow向后走一步
if (slow == fast)//如果相遇
return true;
}
return false;
}
环形链表II
题目链接：LeetCode142.环形链表II
题目:
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。
题目分析：
结论：让一个指针从链表起始位置开始遍历链表，同时让一个指针从偶判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
证明：
题解：
struct ListNode* detectCycle(struct ListNode* head)
{
struct ListNode* slow, * fast;
slow = fast = head;//slow和fast同时指向头结点
while (fast && fast->next)//链表结点可能为奇数也可能为偶数，所以需要这样判断。但判断的条件顺序不能够颠倒。
{
fast = fast->next->next;//fast向后走两步
slow = slow->next;//slow向后走一步
if (slow == fast)//如果相遇
{
struct ListNode* meet = slow;
while (meet != head)
{
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}
方法二：
如果我们想不到上面那个方法，那么这题我们也可以转换成链表相交问题。可以参考上面的相交链表的代码。
struct ListNode* detectCycle(struct ListNode* head)
{
int lenA = 1, lenB = 1;//让最开始的lenA和lenB的值为1，否则计算的链表长度会比实际长度小
struct ListNode* slow, * fast;
slow = fast = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
struct ListNode* meet = slow, * headB, * headA = head;
headB = meet->next;
meet->next = NULL;
struct ListNode* tailA = head, * tailB = headB;
while (tailA->next)
{
tailA = tailA->next;
++lenA;//计算A链表的长度
}
while (tailB->next)
{
tailB = tailB->next;
++lenB;//计算B链表的长度
}
if (tailA != tailB)//如果两个链表的尾结点不相等，那么链表就不相交
return NULL;
//链表相交，求交点。长的链表先走差距步，再同时走找交点。
struct ListNode* shortList = headA, * longList = headB;//定义的时候默认A链表为短链表
if (lenA > lenB)//如果A链表比较长，就小调整一下
{
longList = headA;
shortList = headB;
}
int gap = abs(lenA - lenB);//链表A与链表B的长度差
while (gap--)//让较长的链表先走差距步
{
longList = longList->next;
}
while (shortList && longList)//A链表和B链表都不为空，则进入循环
{
if (shortList == longList)
return shortList;//返回两个链表的交点
shortList = shortList->next;
longList = longList->next;
}
}
}
return NULL;
}
复制带随机指针的链表
题目： 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
- val：一个表示 Node.val 的整数。
- random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
题目分析：
题解：
struct Node* copyRandomList(struct Node* head)
{
//1.拷贝结点连接在原结点的后面
struct Node* cur = head;
while (cur)
{
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));//申请一个结点
copy->val = cur->val;//拷贝原结点的值到拷贝结点中
copy->next = cur->next;//让copy结点指向原结点的下一个结点
cur->next = copy;//原结点指向copy结点
cur = cur->next->next;
}
//2.更新拷贝结点的random
cur = head;
while (cur)
{
struct Node* copy = cur->next;
if (cur->random == NULL)//random为空的情况
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;//拷贝结点的random指向原结点的random的next
}
cur = cur->next->next;
}
//3.将拷贝结点解下来，连接到一起
struct Node* copyHead, * copyTail;
copyHead = copyTail = NULL;//定义一个新链表的头和尾
cur = head;
while (cur)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
cur->next = next;
if (copyTail == NULL)//首结点头插
{
copyTail = copyHead = copy;
}
else
{
copyTail->next = copy;
copyTail = copyTail->next;
}
cur = next;
}
return copyHead;//返回拷贝链表的头结点
}
