下面是本项目的大体思路梳理：
一、实现单链表
全部接口一览：
void SLTPrint(SLTNode* phead);//打印
void SLTPushBack(SLTNode** pphead,SLTDateType x);//尾插
void SLTPushiFront(SLTNode** pphead, SLTDateType x);//头插
void SLTPopBack(SLTNode** pphead);//尾删
void SLTPopFront(SLTNode** pphead);//头删
void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDateType x);//任意位置之前插入
SLTNode* SLTFind(SLTNode** pphead, SLTDateType x);//查找接口
void SLTInsertAfter(SLTNode* pos, SLTDateType x);//任意位置之后插入
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos指向的节点
void SLTEraseAfter(SLTNode* pos);//删除pos指向之后的节点
void SLTDestroy(SLTNode** pphead);//销毁链表接口
1.创建链表的结构体
//定义单链表结构体
#define SLTDateType int
typedef struct SListNode
{
SLTDateType date;//每个节点的数据
struct SListNode* next;//每个节点存储下一个节点的地址
}SLTNode;
2.打印链表的接口实现
首先制造一些节点并进行相连操作
打印函数实现的思路：
void SLTPrint(SLTNode* phead)
{
//定义一个新的指针
SLTNode* pcur = phead;
//循环打印即可，什么时候停止？pcur不指向空便不停止
while (pcur)
{
//打印数据
printf("%d->", pcur->date);
//更新指针
pcur = pcur->next;
}
//为了完善，我给最后也加一个NULL
printf("NULL\n");
}
3.尾插接口实现
思路：定义一个新指针，找到原链表的尾节点，找到了接上即可。
这里为什么要分类进行讨论？这由思路决定的，因为如果是空链表的情况下，ptail->next根本就是错误的，因为不存在。
新空间开辟接口：
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
//申请一块新的空间
SLTNode* newnode = SLTBuyNode(x);
//分两种情况
//链表为空
if (*pphead == NULL)
{
*pphead = newnode;
}
else//链表不为空
{
SLTNode* ptail = *pphead;//用于找到链表的尾节点
while (ptail->next)
{
ptail = ptail->next;
}//找到尾节点
ptail->next = newnode;//给他接上
}
}
SLTNode* SLTBuyNode(SLTDateType x)
{
//申请一块新的空间
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//放内容
newnode->date = x;
newnode->next = NULL;
//返回地址
return newnode;
}
4.头插接口实现
思路：
尾插需要分情况讨论而头插怎么不需要呢？还是思路决定的，这个思路没有用到ptail->next所以就不需要考虑空链表的情况
void SLTPushiFront(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
//申请一块新的空间
SLTNode* newnode = SLTBuyNode(x);
//把原来第一个结点的地址交给新节点的next
newnode->next = *pphead;
*pphead = newnode;//把头部指针更新一下
}
5.尾删接口实现
思路：
这里为什么要分只有一个节点和多个节点的不同情况？因为涉及到prev问题如果是只有一个节点，ptail指向第一个节点，那prev指针指向哪里？所以要对只有一个节点的链表单独进行处理。
void SLTPopBack(SLTNode** pphead)
{
//检验
assert(pphead);//原本的指针不能是空
assert(*pphead);//传过来的不能是空指针给我删除啊
//删除
//这里分两种情况
//1.只有一个节点的情况
if (*pphead == NULL)
{
free(*pphead);
*pphead = NULL;
return;
}
else//多个节点的情况
{
//需要找到最后一个节点和倒数第二个节点
//最后一个节点是为了释放空间
//倒数第二个节点是为了把他的next部分置为空
SLTNode* ptail = *pphead;
SLTNode* prev = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
//第二个节点next置为空
prev->next = NULL;
//销毁第一个节点
free(ptail);
ptail = NULL;
}
}
6.头删接口的实现
思路：
void SLTPopFront(SLTNode** pphead)
{
//检验
assert(pphead);//检验你别给我传个空
assert(*pphead);//检验链表不为空，空链表删除什么？
//开始准备删除
SLTNode* next = (*pphead)->next;//记录一下要接上的地址
free(*pphead);//释放第一个节点
*pphead = next;
}
7.查找接口实现
查找接口是做什么的呢？找一个节点的地址的。
思路实现：
SLTNode* SLTFind(SLTNode** pphead, SLTDateType x)
{
//检查
assert(pphead);//别传空指针进来
//这里可以传空链表吗？可以！顶多找不到给你返回一个NULL嘛
//遍历链表
SLTNode* pcur = *pphead;
while (pcur)//当pcur找到NULL时候就会停止
{
if (pcur->date == x)
{
return pcur;//满足条件，返回该节点的地址
}
pcur = pcur->next;//更新指针
}
//如果什么都没有找到的话，是不是会不太合适\
// 所以我们规定如果没有找到，返回NULL地址
return NULL;
}
8.在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
//检验
assert(pphead);//传入地址不得为空
assert(pos);//pos不得为空
assert(*pphead);//要加上链表不得为空，\
这是因为pos是链表的一个节点的地址，如 \
果链表不存在，那么pos也会不存在
//这里要分情况进行处理
//1.pos刚好是头节点
if (pos == *pphead)
{
//直接调用头插
SLTPushiFront(pphead,x);
return;
}
else//2.如果pos不是头节点
{
SLTNode* prev = *pphead;
//让prev找到pos之前的节点的地址
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = SLTBuyNode(x);//申请空间
prev->next = newnode;//把新空间链接到我们前一个节点
newnode->next = pos;//把新空间与pos指向的空间链接在一起
}
}
9.在指定位置之后插入数据的接口实现
思路：
思考：上面说的关联新节点的错误是如何引起的呢？
答：因为新节点的后面的节点的地址表示是靠的pos->next
void SLTInsertAfter(SLTNode* pos, SLTDateType x)//之后
{
//检查
assert(pos);
//申请空间
SLTNode* newnode = SLTBuyNode(x);
//关联新节点的错误写法，原因：pos值的改变
//pos->next = newnode;
//newnode->next = pos->next;
//关联新节点的正确写法：
//先接后面，再接前面
newnode->next = pos->next;
pos->next = newnode;
}
10.删除指定位置的节点
思路：
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
//检查
assert(pphead);//不得传空
assert(*pphead);//不得为空链表
assert(pos);
//pos刚好是头节点的情况，头删
if (*pphead == pos)
{
//头删
SLTPopFront(pphead);
return;
}
//如果不是头节点
else {
//找到pos之前的节点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
11.删除指定位置之后的节点接口实现
思路：
void SLTEraseAfter(SLTNode* pos)
{
//检查
assert(pos);//传过来的地址不可以为空
assert(pos->next);//传过来的地址的下一个地址不得为空
SLTNode* del = pos->next;//记录要删除的节点的地址
pos->next = pos->next->next;//更新pos中next的地址
free(del);//释放空间
del = NULL;//临时指针及时置为空
}
12.销毁链表接口
思路：
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);//传过来的指针不得为空
assert(*pphead);//链表不得为空，空链表不用销毁
//创建遍历指针
SLTNode* pcur = *pphead;
//循环销毁
while (pcur)//啥时候停止？pcur指向NULL
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//最后把头指针也置为NULL
*pphead = NULL;
}
全部代码合集
//SList.h
#pragma once
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
//定义单链表结构体
#define SLTDateType int
typedef struct SListNode
{
SLTDateType date;//每个节点的数据
struct SListNode* next;//每个节点存储下一个节点的地址
}SLTNode;
void SLTPrint(SLTNode* phead);//打印
void SLTPushBack(SLTNode** pphead,SLTDateType x);//尾插
void SLTPushiFront(SLTNode** pphead, SLTDateType x);//头插
void SLTPopBack(SLTNode** pphead);//尾删
void SLTPopFront(SLTNode** pphead);//头删
void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDateType x);//任意位置之前插入
SLTNode* SLTFind(SLTNode** pphead, SLTDateType x);//查找接口
void SLTInsertAfter(SLTNode* pos, SLTDateType x);//任意位置之后插入
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos指向的节点
void SLTEraseAfter(SLTNode* pos);//删除pos指向之后的节点
void SLTDestroy(SLTNode** pphead);//销毁链表接口
//SList.c
#include"SList.h"
SLTNode* SLTBuyNode(SLTDateType x)
{
//申请一块新的空间
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//放内容
newnode->date = x;
newnode->next = NULL;
//返回地址
return newnode;
}
SLTNode* SLTFind(SLTNode** pphead, SLTDateType x)
{
//检查
assert(pphead);//别传空指针进来
//这里可以传空链表吗？可以！顶多找不到给你返回一个NULL嘛
//遍历链表
SLTNode* pcur = *pphead;
while (pcur)//当pcur找到NULL时候就会停止
{
if (pcur->date == x)
{
return pcur;//满足条件，返回该节点的地址
}
pcur = pcur->next;//更新指针
}
//如果什么都没有找到的话，是不是会不太合适\
// 所以我们规定如果没有找到，返回NULL地址
return NULL;
}
void SLTPrint(SLTNode* phead)
{
//定义一个新的指针
SLTNode* pcur = phead;
//循环打印即可，什么时候停止？pcur不指向空便不停止
while (pcur)
{
//打印数据
printf("%d->", pcur->date);
//更新指针
pcur = pcur->next;
}
//为了完善，我给最后也加一个NULL
printf("NULL\n");
}
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
//申请一块新的空间
SLTNode* newnode = SLTBuyNode(x);
//分两种情况
//链表为空
if (*pphead == NULL)
{
*pphead = newnode;
}
else//链表不为空
{
SLTNode* ptail = *pphead;//用于找到链表的尾节点
while (ptail->next)
{
ptail = ptail->next;
}//找到尾节点
ptail->next = newnode;//给他接上
}
}
void SLTPushiFront(SLTNode** pphead, SLTDateType x)
{
assert(pphead);
//申请一块新的空间
SLTNode* newnode = SLTBuyNode(x);
//把原来第一个结点的地址交给新节点的next
newnode->next = *pphead;
*pphead = newnode;//把头部指针更新一下
}
void SLTPopBack(SLTNode** pphead)
{
//检验
assert(pphead);//原本的指针不能是空
assert(*pphead);//传过来的不能是空指针给我删除啊
//删除
//这里分两种情况
//1.只有一个节点的情况
if (*pphead == NULL)
{
free(*pphead);
*pphead = NULL;
return;
}
else//多个节点的情况
{
//需要找到最后一个节点和倒数第二个节点
//最后一个节点是为了释放空间
//倒数第二个节点是为了把他的next部分置为空
SLTNode* ptail = *pphead;
SLTNode* prev = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
//第二个节点next置为空
prev->next = NULL;
//销毁第一个节点
free(ptail);
ptail = NULL;
}
}
void SLTPopFront(SLTNode** pphead)
{
//检验
assert(pphead);//检验你别给我传个空
assert(*pphead);//检验链表不为空，空链表删除什么？
//开始准备删除
SLTNode* next = (*pphead)->next;//记录一下要接上的地址
free(*pphead);//释放第一个节点
*pphead = next;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
//检验
assert(pphead);//传入地址不得为空
assert(pos);//pos不得为空
assert(*pphead);//要加上链表不得为空，
//这是因为pos是链表的一个节点的地址，如
//果链表不存在，那么pos也会不存在
//这里要分情况进行处理
//1.pos刚好是头节点
if (pos == *pphead)
{
//直接调用头插
SLTPushiFront(pphead,x);
return;
}
else//2.如果pos不是头节点
{
SLTNode* prev = *pphead;
//让prev找到pos之前的节点的地址
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = SLTBuyNode(x);//申请空间
prev->next = newnode;//把新空间链接到我们前一个节点
newnode->next = pos;//把新空间与pos指向的空间链接在一起
}
}
void SLTInsertAfter(SLTNode* pos, SLTDateType x)//之后
{
//检查
assert(pos);
//申请空间
SLTNode* newnode = SLTBuyNode(x);
//关联新节点的错误写法，原因：pos值的改变
//pos->next = newnode;
//newnode->next = pos->next;
//关联新节点的正确写法：
//先接后面，再接前面
newnode->next = pos->next;
pos->next = newnode;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
//检查
assert(pphead);//不得传空
assert(*pphead);//不得为空链表
assert(pos);
//pos刚好是头节点的情况，头删
if (*pphead == pos)
{
//头删
SLTPopFront(pphead);
return;
}
//如果不是头节点
else {
//找到pos之前的节点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
void SLTEraseAfter(SLTNode* pos)
{
//检查
assert(pos);//传过来的地址不可以为空
assert(pos->next);//传过来的地址的下一个地址不得为空
SLTNode* del = pos->next;//记录要删除的节点的地址
pos->next = pos->next->next;//更新pos中next的地址
free(del);//释放空间
del = NULL;//临时指针及时置为空
}
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);//传过来的指针不得为空
assert(*pphead);//链表不得为空，空链表不用销毁
//创建遍历指针
SLTNode* pcur = *pphead;
//循环销毁
while (pcur)//啥时候停止？pcur指向NULL
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//最后把头指针也置为NULL
*pphead = NULL;
}
//test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void test1()
{
//头指针
SLTNode* phead = NULL;
//造一点结点
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
node1->date = 1;
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
node2->date = 2;
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
node3->date = 3;
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
node4->date = 4;
SLTNode* node5 = (SLTNode*)malloc(sizeof(SLTNode));
node5->date = 5;
//链接这些节点
phead = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
node5->next = NULL;
//调用一下打印函数
SLTPrint(phead);
}
void test2()
{
SLTNode* phead = NULL;
SLTPushBack(&phead,6);
SLTPrint(phead);
SLTPushiFront(&phead,0);
SLTPushiFront(&phead,1);
SLTPushiFront(&phead,2);
SLTPushiFront(&phead,3);
SLTPushiFront(&phead,4);
SLTPushiFront(&phead,5);
SLTPrint(phead);//5->4->3->2->1->0->6->NULL
SLTPopBack(&phead);
SLTPrint(phead);//5->4->3->2->1->0->NULL
SLTPopFront(&phead);
SLTPopFront(&phead);
SLTPopFront(&phead);
SLTPopFront(&phead);
SLTPrint(phead);//1->0->NULL
SLTNode* find = SLTFind(&phead,1);
SLTInsert(&phead, find, 2);
SLTPrint(phead);//2->1->0->NULL
SLTInsertAfter(find, 8);
SLTPrint(phead);//2->1->8->0->NULL
SLTEraseAfter(find);
SLTPrint(phead);//2->8->0->NULL
SLTDestroy(&phead);
SLTPrint(phead);//NULL
}
int main()
{
//测试我的打印函数
//test1();
//测试我的插入与删除函数
test2();
return 0;
}
二、相关练习题
1.中间链表
题目链接：LINK
详细解答：LINK
struct ListNode* middleNode(struct ListNode* head) {
//思路1：暴力求解法
/*int length = 0;
struct ListNode* pcur = head;
while(pcur)
{
length++;
pcur = pcur->next;
}
length/=2;
pcur = head;
while(length--)
{
pcur = pcur->next;
}
return pcur;
*/
//思路2：双指针法
struct ListNode* slow = head;
struct ListNode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
2.删除链表中等于给定值 val 的所有结点
题目链接：LINK
多种解题思路：LINK
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
//处理*head == val 的情况，使*head！=val
while (head && head->val == val)
{
head = head->next;
}
//如果是空链表，返回
if(head == NULL)
{
return NULL;
}
//走到这里，head不是val并且该链表不为空
struct ListNode* cur = head->next;//如果head为空链表这样写不合法
struct ListNode* pre = head;
while (cur != NULL) {
if (cur->val == val)
{
//跳跃
pre->next = cur->next;
//free
struct ListNode* temp = cur;
}
else
{
//下一个跟进cur
pre = cur;
}
//cur不断向前走
cur = cur->next;
}
return head;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
//定义新链表的头尾指针
struct ListNode* newHead = NULL;
struct ListNode* newTail = NULL;
//
struct ListNode* pcur = head;
while(pcur)
{
//不是val，尾插到新链表
if(pcur->val!=val)
{
if(newHead == NULL)
{
//链表为空
newHead = newTail = pcur;
}
else//链表不为空
{
newTail->next = pcur;
newTail = newTail->next;//更新尾节点
}
}
//更新pcur指针
pcur = pcur->next;
}
//加上null
if(newTail)
{
newTail->next = NULL;
}
//返回
return newHead;
}
3.反转链表
题目链接：LINK
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
//防止给我一个空的链表,如果说给我一个空链表，那么我们下面的n2->next会报错
if(head == NULL)
return head;
//指针初始化
struct ListNode* n1 = NULL;
struct ListNode* n2 = head;
struct ListNode* n3 = n2->next;
while(n2)
{
n2->next = n1;//改变指向
n1 = n2;
n2 = n3;
if(n3)//如果n3不为空，那么让n3往下走一个
n3 = n3->next;
}
return n1;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
//头插的思路
struct ListNode* newhead = NULL;
struct ListNode* pcur = head;
while(pcur)
{
struct ListNode* next = pcur->next;
pcur->next = newhead;
newhead = pcur;
pcur = next;
}
return newhead;
}
4.分割链表
题目链接：LINK
#include<stdio.h>
#include<stdlib.h>
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// write code here
//申请哨兵位置
struct ListNode* sentry1 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* sentry2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//定义指针
struct ListNode* newhead1,*newhead2,*newtail1,*newtail2;
newhead1 = newtail1 = sentry1;
newhead2 = newtail2 = sentry2;
//按照条件分割
struct ListNode* pcur = pHead;
while(pcur)
{
if(pcur->val<x)
{
newtail1->next = pcur;
newtail1 = newtail1->next;
}
else
{
newtail2->next = pcur;
newtail2 = newtail2->next;
}
pcur = pcur->next;
}
//链接list1与list2
newtail1->next = newhead2->next;
newtail2->next = NULL;
pHead = newhead1->next;
free(newhead1);
free(newhead2);
return pHead;
}
};
5.链表中倒数第K个结点
题目链接：LINK
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
int kthToLast(struct ListNode* head, int k){
struct ListNode* pcur = head;
int count = 0;
while(pcur)
{
count++;
pcur = pcur->next;
}
count = count - k;
pcur = head;
while(count--)
{
pcur = pcur->next;
}
return pcur->val;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
int kthToLast(struct ListNode* head, int k){
struct ListNode* slow = head;
struct ListNode* fast = head;
while(k--)
{
fast = fast->next;
}
while(fast)
{
slow = slow->next;
fast = fast->next;
}
return slow->val;
}
6.合并链表
题目链接：LINK
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//考虑空链表的情况：
//1.两个链表都是空的
if(list1 == NULL && list2 == NULL)
{
return NULL;
}
//2.只有list1是空的
if(list1 == NULL)
{
return list2;
}
//3.只有list2是空的
if(list2 == NULL)
{
return list1;
}
//走到这里，就说明两个链表都不为空了。
struct ListNode* head = NULL;
struct ListNode* tail = NULL;
//定义两个指针分别遍历两个链表
struct ListNode* pcur1 = list1;
struct ListNode* pcur2 = list2;
while(pcur1 && pcur2)
{
if(pcur1->val < pcur2->val)
{
if(head == NULL)
{
head = tail = pcur1;
}
else
{
tail->next = pcur1;
tail = pcur1;
}
pcur1 = pcur1->next;
}
else
{
if(head == NULL)
{
head = tail = pcur2;
}
else
{
tail->next = pcur2;
tail = pcur2;
}
pcur2 = pcur2->next;
}
}
//走到这里，会出现两种情况，要不剩下list1，要不剩下list2
while(pcur1)
{
tail->next = pcur1;
tail = pcur1;
pcur1 = pcur1->next;
}
while(pcur2)
{
tail->next = pcur2;
tail = pcur2;
pcur2 = pcur2->next;
}
return head;
}
7.链表的回文结构
题目链接：LINK
详细解答：LINK
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
//找到中间结点
struct ListNode* middleNode(struct ListNode* head) {
//思路2：快慢指针法
struct ListNode* fast = head;
struct ListNode* slow = head;
while(fast && fast->next)//快指针走到头
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
//逆置链表为空
if(head == nullptr)
return head;
//不为空
struct ListNode* n1 = nullptr;
struct ListNode* n2 = head;
struct ListNode* n3 = head->next;
while(n2)
{
//逆置
n2->next = n1;
//移动n1、n2、n3指向下一个
n1 = n2;
n2 = n3;
if(n3)//n3不为空
{
n3 = n3->next;
}
}
return n1;
}
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
//找到中间节点
struct ListNode* pMidNode = middleNode(A);
//逆置中间节点及其以后的节点
struct ListNode* pNewMidNode = reverseList(pMidNode);
//对比
while(A&&pNewMidNode)
{
if(pNewMidNode->val!=A->val)
{
return false;
}
//向后走
A = A->next;
pNewMidNode = pNewMidNode->next;
}
return true;
}
};
8.查找相交结点
题目链接：LINK
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
#include<math.h>
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
//判断是不是相交链表
struct ListNode* pTailA = headA;
struct ListNode* pTailB = headB;
int skipA = 0;//统计A链表中结点的个数
int skipB = 0;//统计B链表中结点的个数
//统计结点个数
while(pTailA->next)
{
pTailA=pTailA->next;
skipA++;
}
skipA++;//统计少了一个，给他加上
while(pTailB->next)
{
pTailB=pTailB->next;
skipB++;
}
skipB++;
//不是交点
if(pTailA!=pTailB)
{
return NULL;
}
//如果是，那么证明他们一定是相交的了，所以我们要查找出他的交点
int sub = abs(skipA-skipB);
struct ListNode* pmin = NULL;
struct ListNode* pmax = NULL;
if(skipA<skipB)
{
pmin = headA;
pmax = headB;
}
else
{
pmin = headB;
pmax = headA;
}
//让长的先走一些，让长短对齐
while(sub--)
{
pmax = pmax->next;
}
//找交点
while(pmin!=pmax)
{
pmin = pmin->next;
pmax = pmax->next;
}
return pmax;
}
9.判断有环链表
题目链接：LINK
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode* fast = head;
struct ListNode* slow = head;
while(fast&&fast->next)
{
slow=slow->next;
fast = fast->next->next;
if(fast == slow)
{
return true;
}
}
return false;
}
10.有环链表找入环结点
题目链接：LINK
/**
* 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)
{
slow=slow->next;
fast = fast->next->next;
if(fast == slow)
{
struct ListNode * meet = slow;
struct ListNode * headx = head;
while(meet!=headx)
{
meet = meet->next;
headx = headx->next;
}
return meet;
}
}
return NULL;
}
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
//首先统计每个链表结点的个数
int count1 = 0;
int count2 = 0;
struct ListNode *pcur1 = headA,*pcur2 = headB;
while(pcur1)
{
count1++;
pcur1 = pcur1->next;
}
while(pcur2)
{
count2++;
pcur2 = pcur2->next;
}
struct ListNode *maxhead = headA;
struct ListNode *minhead = headB;
if(count1 < count2)
{
maxhead = headB;
minhead = headA;
}
int sub = count1-count2;
if(sub<0)
{
sub = 0-sub;
}
while(sub--)
{
maxhead = maxhead->next;
}
while(minhead!=maxhead)
{
minhead = minhead->next;
maxhead = maxhead->next;
}
return maxhead;
}
struct ListNode *detectCycle(struct ListNode *head) {
//方法二：转换题目：相交链表
struct ListNode* slow = head,*fast = head;
while(fast&&fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
struct ListNode* head1 = slow->next;
struct ListNode* head2 = head;
slow->next = NULL;
struct ListNode* meet = getIntersectionNode(head1,head2);
return meet;
}
}
return NULL;
}
11.随机链表的复制
题目链接：LINK
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
struct Node* copyRandomList(struct Node* head) {
if(head==NULL)
{
return NULL;
}
struct Node* pcur = head;
//插入一些复制结点
while(pcur)
{
struct Node* pushback = (struct Node*)malloc(sizeof(struct Node));
pushback->val = pcur->val;
pushback->next = pcur->next;
pcur->next = pushback;
pcur = pcur->next->next;//调整pcur
}
//控制拷贝结点的random
pcur = head;
while(pcur)
{
//如果原链表的random指向空，那我们新链表也要指向空
if(pcur->random == NULL)
{
pcur->next->random = NULL;
pcur = pcur->next->next;
continue;
}
pcur->next->random = pcur->random->next;
pcur = pcur->next->next;
}
//把拷贝结点放下来
pcur = head;
struct Node* pcurx = head->next;
struct Node* returnpcurx = pcurx;
while(pcur)
{
pcur->next = pcur->next->next;
pcur = pcur->next;
//最后一个节点
if(pcurx->next == NULL)
{
pcurx->next = NULL;
break;
}
pcurx->next = pcurx->next->next;
pcurx = pcurx->next;
}
//返回
return returnpcurx;
}
EOF
