简简单单拿捏单链表
会介绍单链表的增删查改等功能，在后面讲解一些链表比较经典的面试OJ题（相交、逆序、找中间节点、成环链表）
内容很多很干，请大家多多支持
?
目录
头文件部分
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data; // val
struct SListNode* next; // 存储下一个节点的地址
}SListNode;
头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newcode = BuySListNode(x);
newcode->next = *pphead;
*pphead = newcode;
}在开头插入比较简单，将头节点指向新节点，新节点和原来的第一个节点连接即可，这里的BuyListNode是创建新节点的函数，且会初始化好节点（传入x）
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newcode = (SListNode*)malloc(sizeof(SListNode));
if (newcode == NULL)
{
printf("开辟失败\n");
exit(-1);
}
else
{
newcode->data = x;
newcode->next = NULL;
}
return newcode;
}头删
void SListPopFront(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)
return;
else
{
SListNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
}如果第一个节点为空则没有要删除的，直接返回
尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newcode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newcode;
}
else
{
SListNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newcode;
}
}找尾结点的方式用的是找tail->next为NULL时而不是tail为NULL时，如果用后者则导致新节点无法连接（函数中形参的改变不影响实参）
尾删
void SListPopBack(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)
{
return;
}
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SListNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
注意这里找的是tail->next->next为空的时候，也就是要删除的节点的前一个节点
指定位置前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SListNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}指定位置前删除
void SListErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SListPopFront(pphead);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}指定位置后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newcode = BuySListNode(x);
newcode->next = pos->next;
pos->next = newcode;
}指定位置后删除
void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* next = pos->next;
if (next)
{
pos->next = next->next;
free(next);
next = NULL;
}
}查找（修改）
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
SListNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}销毁（释放空间）
void SListDestroy(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
?学完单链表基础操作来挑战OJ题！
一些OJ题
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while (cur)
{
if (cur->val != val)
{
prev = cur;
cur = cur->next;
}
else
{
struct ListNode* next = cur->next;
if (prev == NULL)
{
free(cur);
head = next;
cur = next;
}
else
{
free(cur);
prev->next = next;
cur = next;
}
}
}
return head;
}定义三个节点，分别指向前、现在、下一个链表节点，迭代遍历链表，如果cur目前的val不需要删除，则将指针均向后移，如果需要删除则分两种情况，如果当前所需要删除的是头节点，则需要先让头节点指向下一个节点，然后再后移指针，如果不是头结点，则释放后进行后移即可
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;
}这里还是定义三个指针，分别指向现在，上一个和下一个节点，和上一题思路类似
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点??????
?
struct ListNode* middleNode(struct ListNode* head)
{
int i=0;
struct ListNode* cur=head;
while(cur)
{
i++;
cur=cur->next;
}
int flag=i/2+1;
i=0;
cur=head;
while(cur)
{
i++;
if(i==flag)
break;
cur=cur->next;
}
return cur;
}3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点??????第一种思路，用计数法遍历两次，第一次找出链表长度，第二次找到中间节点
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}第二种思路，快慢指针，快指针走两步，慢指针走一步，注意这里循环的判断条件，首先有两个，并且必须是fast在前面(&&运算时如果第一个判定为假则后面就不判断了，直接判定条件为假)，如果有偶数个节点，则要求返回下中位数，当fast为NULL时结束循环，此时slow正好在第三个位置。如果有奇数个节点，当fast->next为空时，也就是fast走到最后一个节点时结束。现在如果while条件改成这样
while(fast->next && fast)如果头结点为空，那这种写法就造成了内存越界，而上一种写法因为fast已经为假因此不会判断&&后的fast->next，因此避免了这种错误。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
struct ListNode* fast=pListHead;
struct ListNode* slow=pListHead;
while(k--)
{
if(fast==NULL)
return NULL;
fast=fast->next;
}
while(fast)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}仍然运用快慢指针，这里让fast指针先走k步，然后再让slow和fast同时开始走，那么在fast为NULL时，slow就走了n-k步，到达倒数第n个节点，这里在fast先走的情况下如果fast提前为空则要提前返回，比如说一共有5个节点，要找倒数第6个，6>5,则要找的这个一定为空，则直接返回空
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
?
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1==NULL)
return list2;
if(list2==NULL)
return list1;
struct ListNode* head;
struct ListNode* tail;
head=tail=(struct ListNode*)malloc(sizeof (struct ListNode));
while(list1&&list2)
{
if(list1->val>list2->val)
{
tail->next=list2;
tail=tail->next;
list2=list2->next;
}
else
{
tail->next=list1;
tail=tail->next;
list1=list1->next;
}
}
if(list1)
{
tail->next=list1;
}
if(list2)
{
tail->next=list2;
}
struct ListNode* newhead=head->next;
free(head);
return newhead;
}
这里用了哨兵位头节点，遍历list1和list2，找出小的节点连接到新链表上，较大的不动，当list1和list2中的一个遍历完时，将另一个链表的所有节点直接连接到新节点的尾上。最后释放哨兵位，返回新的头节点。
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
?
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// write code here
struct ListNode* lesstail,*lesshead,*greatertail,*greaterhead=NULL;
lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
greaterhead=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));
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;
}
greatertail->next=NULL;
lesstail->next=greaterhead->next;
struct ListNode* newhead=lesshead->next;
free(lesshead);
free(greaterhead);
return newhead;
}
};
这种方法设置哨兵位头节点，整体思路和上一题差不多，记得最后要将较大链表的尾制空。同时因为有哨兵位，因此less链表的尾和great链表的头连接的时候要连接greathead->next，也就是哨兵位的下一个节点。
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
if(pHead==NULL)
return NULL;
struct ListNode* lesstail=NULL,*lesshead=NULL,*greatertail=NULL,*greaterhead=NULL;
struct ListNode* cur=pHead;
while(cur)
{
if(cur->val<x)
{
if(lesstail==NULL)
{
lesshead=lesstail=cur;
}
else
{
lesstail->next=cur;
lesstail=lesstail->next;
}
}
else
{
if(greatertail==NULL)
{
greaterhead=greatertail=cur;
}
else
{
greatertail->next=cur;
greatertail=greatertail->next;
}
}
cur=cur->next;
}
if(lesshead && greaterhead)
{
greatertail->next=NULL;
lesstail->next=greaterhead;
}
else if(lesshead==NULL)
{
return greaterhead;
}
return lesshead;
}
};这里不用哨兵位头结点，比较麻烦，在新链表连接时要判断是否为对头节点连接并做不同处理。且最后返回的时候要考虑特殊情况，如果链表所有的元素都比所给元素大，则less链表的头为空，因此就要返回great链表的头，如果原链表为空则直接返回空。
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
struct ListNode* slow,*fast,*prev,*cur,*next;
slow=fast=A;
while(fast&&fast->next)//找中间节点
{
slow=slow->next;
fast=fast->next->next;
}
cur=slow;
prev=NULL;
while(cur)//对中间节点后半部分逆序
{
next=cur->next;
cur->next=prev;
prev=cur;
cur=next;
}
while(A&&prev)
{
if(A->val!=prev->val)
return false;
A=A->next;
prev=prev->next;
}
return true;
}
};这个题的思路是先找到中间节点，将链表一分为二，然后逆置后半部分，再逐一开始比较，那如果链表有奇数个元素，这样处理后后半部分有3个元素，而前半部分只有两个元素，这里是怎么处理的呢？
?这里看到，当我们逆置后，前半部分也就是2的尾仍然指向3，这是没有改变的，相当于前半部分的最后一个节点也是3，因此可以这样比较。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
struct ListNode* tailA=headA;
struct ListNode* tailB=headB;
int lenA=1;
int lenB=1;//记录长度
while(tailA->next)//找尾看是否相同判断是否有交点
{
tailA=tailA->next;
lenA++;
}
while(tailB->next)
{
tailB=tailB->next;
lenB++;
}
if(tailA!=tailB)
return NULL;
struct ListNode* longlist=headA;
struct ListNode* shortlist=headB;
int n=abs(lenA-lenB);//让长的先走
if(lenA<lenB)
{
longlist=headB;
shortlist=headA;
}
while(n--)//长的先走
longlist=longlist->next;
while(longlist!=shortlist)//一起走，相等时就返回
{
longlist=longlist->next;
shortlist=shortlist->next;
}
return shortlist;
}
?这个题的思路是两个指针从头开始遍历，如果两个链表有交点的话，那他们的尾一定是一样的，如果不一样则没相交。判断第一个相交节点在哪的时候，以图中为例，B链表比A链表长了1个节点，因此让B先走一步，那现在相当于A，B链表剩余的节点数是一样的，同时开始往后遍历，如果遇到相等的第一个节点就返回该节点，就找到了第一个相交点。
到这里难度是不是还尚可，接下来要提难度咯
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;
}
用快慢指针法，假设当slow进环的时候，fast肯定已经进了环了，如果圈比较大，fast可能没走完一圈，如果环比较小，fast可能已经走了很多圈，这些我们不考虑，我们就考虑此时此刻fast和slow的距离是N，fast和slow每次缩小1的距离，那么最后fast一定能追上slow，而且一定是在slow走完半圈前追上它，因此slow如果走了半圈，那fast已经走了一圈，一定会超过slow一次。因此可以写出上面的代码，下一个题来求出入环的入口在哪里
10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
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(slow==fast)
{
struct ListNode* meet=slow;//相遇点
while(meet!=head)
{
meet=meet->next;
head=head->next;
}//相等的时候说明到了入环口了
return meet;
}
}
return NULL;
}
?先来推导一个公式，由上一题的推导，我们现在假设在fast追上slow的时候，slow走了L+X步，那fast就走了2（L+X）步，fast还可以怎么表示呢？刚刚说了在slow进圈的时候根据环的大小fast可能没走完一圈，也可能已经走了很多圈，也就是fast走了L+N*C+X（N表示圈数）步，那么就有2（L+X）=L+N*C+X，进行移项化简可以得到L=N*C-X，对这个式子再整理一下，L=(N-1)C+(C-X)，也就是说，假设一个指针从链表头开始走，一个指针从相遇点开始走，那么他们最后会在入环口相遇（不管N等于几），因此写出上述代码。
11. 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深度拷贝
?
struct Node* copyRandomList(struct Node* head)
{
struct Node* cur=head;
while(cur)//在链表每个节点后拷贝的节点
{
struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
newnode->next=cur->next;
newnode->val=cur->val;
cur->next=newnode;
cur=newnode->next;
}
cur=head;
while(cur)//拷贝random节点，新链表指向的random恰好在原链表random的后面
{
struct Node* copy=cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=cur->next->next;
}
//修复原链表和现链表
cur=head;
struct Node* newhead=NULL;
struct Node* newtail=NULL;
while(cur)
{
struct Node* copy=cur->next;
if(newtail==NULL)
{
newhead=newtail=copy;
}
else
{
newtail->next=copy;
newtail=newtail->next;
}
cur->next=copy->next;
cur=copy->next;
}
return newhead;
}
这道题是最难的一道，综合考察了链表的知识
做这个题分为三步：
1.拷贝节点连接在原节点后面
2.链接节点的random
3.剪切链表，链接新链表
?结合这张图，这么做的原因是在找random的时候，比如第二个节点的random指向第一个节点7，那么新的拷贝节点的random也要指向新建立的链表的第一个节点7，而这个7恰好在第二个节点random的后面（有点绕，理解一下），就将找random化难为易。
?单链表至此结束，相信如果看到这里的你一定受益匪浅！
?