注意OJ题，传过来的一般是指向头结点的头指针，而非带哨兵卫的头结点。
文章目录
一.移除链表元素
解题思路1：不建立哨兵卫
（1）着重利用到两个指针，cur（即当前位置，去寻找值为val的重要指针），prev（指向cur前面的一个结点），利用这两个指针移除链表中的特定元素。
（2）刚开始cur指向头结点，而prev被初始化为NULL（不然就会沦为野指针），cur会在每次循环后，遍历移向下一个结点，所以当cur为NULL时，跳出循环，如果cur指向的结点值不为val，则cur跳过此结点，指向下一个结点，在这步指向之前，要把cur的位置先赋给prev。
（3）当cur指向的结点值为val，则要删除当前结点。在这里分为两种情况，要删除的是头结点，和不是头结点。如果是头结点，第一步替换头结点，head=head->next;第二步：释放头结点，free（cur），第三步：重置cur，cur=head。如果不是头结点，第一步断开连接，让prev->next=cur->next,第二步释放次结点，free(cur),第三步cur指向此节点的下一个结点，即cur=prev->next;
>图解：
代码实现：
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* cur=head,*prev=NULL;
while(cur)
{
if(cur->val==val)
{
//1.头删
if(cur==head)
{
head=head->next;
free(cur);
cur=head;
}
//2.非头删
else
{
prev->next=cur->next;
free(cur);
cur=prev->next;
}
}
else
{
prev=cur;
cur=cur->next;
}
}
return head;
}
解题思路2：建立新链表
解题思路：
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* cur=head;
struct ListNode* newhead=NULL,*tail=NULL;
while(cur)
{
if(cur->val!=val)
{
if(tail==NULL)
{
newhead=tail=cur;
}
else
{
tail->next=cur;
tail=tail->next;
}
cur=cur->next;
}
else
{
struct ListNode* del=cur;
cur=cur->next;
free(del);
}
}
//最后一个结点为val时，注意将最后一个结点的指针域指向空
if(tail)
{
tail->next=NULL;
}
return newhead;
}
解题思路3：建立哨兵卫
带哨兵卫后（头结点，但只有指针域），代码变得更加简洁，建立新链表时，不需要判断tail是否为NULL，让tail=guard后，即可连接符合条件的结点。一定要记住，若最后一个结点为val，要记住把tail->next==NULL。
*注意我们建立的新节点最后也需要释放。并且最开始要把guard->next置为空，不然它将会是一个野指针，当传过来的是空链表，那么程序就会报错。
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* cur=head;//cur勇于遍历原链表
struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode));
guard->next=NULL;//若原链表为NULL
struct ListNode* tail=guard;//tail指向头结点
while(cur)
{
if(cur->val!=val)
{
tail->next=cur;//连接符合条件的结点
tail=tail->next;//更新tail
cur=cur->next;//更新cur
}
else
{
struct ListNode* del=cur;//保存val的位置
cur=cur->next;
free(del);
}
}
//最后结点为val
if(tail)
{
tail->next=NULL;
}
head=guard->next;
free(guard);
return head;
}
二.合并两个有序链表
解题思路：创建新的链表
（1）两个指针分别遍历两个链表
（2）建立哨兵卫，tail尾指针，cur->val较小值进行连接，注意指针指向的更新。
（3）注意有一个有序链表会先连接完成，那么会退出循环，注意我们还需要将剩下一个链表的其余结点连接上去
（4）注意释放哨兵卫的头结点
（5）若传过来的是空链表，那么刚开始我们要把guard->next置为空，不然它将沦为野指针。
（6）这里因为原链表最后已置为空，不像上道题目一样，可能会把最后一个结点删除，所以我们不用考虑这层。
代码实现
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode* guard=(struct ListNode* )malloc(sizeof(struct ListNode));
guard->next=NULL;
struct ListNode* cur1=list1,* cur2=list2;
struct ListNode* tail=guard;
while(cur1&&cur2)
{
if(cur1->val<cur2->val)
{
tail->next=cur1;
cur1=cur1->next;
}
else
{
tail->next=cur2;
cur2=cur2->next;
}
tail=tail->next;
}
if(cur1)
{
tail->next=cur1;
}
if(cur2)
{
tail->next=cur2;
}
struct ListNode* head=guard->next;
free(guard);
return head;
}
三.翻转链表
解题思路1：头插
（1）定义一个新的指针newnode,进行头插，注意更新头指针。
（2）两个指针cur，next，用于前后遍历原链表，next指针用于保存cur下一个结点的位置，cur是要进行头插的结点。注意每次循环都要更新这两个指针的位置。
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur=head;
struct ListNode* newnode = NULL;
while(cur)
{
struct ListNode* next=cur->next;//保留cur下一个结点的地址
cur->next=newnode;
newnode=cur;
cur=next;
}
return newnode;
}
解题思路2：翻转
（1）需要3个辅助指针，当n2指向NULL时跳出循环；
（2）三个指针进行迭代
（3）注意传过来的若为空指针，n3不能直接置成，n3=n2->next,这是错误的示范。所以要先判断n2是否为NULL。
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* n1,*n2,*n3;
n1=NULL;
n2=head;
n3=NULL;
while(n2)
{
n3=n2->next;
n2->next=n1;
//迭代
n1=n2;
n2=n3;
}
return n1;
}
四.链表的中间结点
解题思路1：遍历
因为这道题目没有时间复杂度的要求，所以要解决这道题，我们只需要先遍历一遍链表，统计链表的结点个数，然后再遍历一遍链表，寻找中间结点即可。此方法的时间复杂度为o(n^2)。
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* cur=head;
int count=0;
while(cur)//遍历链表
{
count++;
cur=cur->next;
}
int mid=count/2;
struct ListNode* midnode=head;
while(mid--)
{
midnode=midnode->next;
}
return midnode;
}
解题思路2：快慢指针
我们也可以只遍历一遍链表，就找到中间结点，这样时间复杂度就为O(n).
利用的方法是快慢指针。那么什么是快慢指针呢？
快指针一次走两步，慢指针一次走一步，那么当快指针走到空时，慢指针走到一半，之后返回慢指针指向的地址即可。
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast,*slow;
fast=slow=head;
while(fast&&fast->next)
{
slow=slow->next;//慢指针走一步
fast=fast->next->next;//快指针走两步
}
return slow;
}
五.链表中倒数第k个结点
要求只遍历一遍，即时间复杂度为O(n).
方法：利用快慢指针
fast先走k步
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
struct ListNode* fast,*slow;
fast=slow=pListHead;
//while(--k)// k-1步
while(k--)//k步
{
//1.传过来的是空链表
//2.k>=结点数
if(fast==NULL)
{
return NULL;
}
fast=fast->next;
}
while(fast)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
六.链表分割
测试用例：
（1）普通情况
（2）当最后一个小于x时，会造成环状，最后返回的是val4这个结点，所以val7的结点一定要置为空
（3）当传过来的为空指针，我们的输出也为{}空，所以防止 lessTail->next=greaterGuard->next;出错，我们一开始得把新建的两个哨兵卫结点的next置NULL
class Partition {
public:
ListNode* partition(ListNode* pHead, int x)
{
struct ListNode* lessGuard,*lessTail,*greaterGuard,*greaterTail;
lessGuard=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
greaterGuard=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
//注意置空
lessGuard->next=NULL;
greaterGuard->next=NULL;
//cur遍历原链表
struct ListNode* cur=pHead;
while(cur)
{
if(cur->val<x)
{
lessTail->next=cur;//连接符合条件的cur
lessTail=lessTail->next;//更新指针
}
else
{
greaterTail->next=cur;
greaterTail=greaterTail->next;
}
cur=cur->next;
}
//连接俩链表
lessTail->next=greaterGuard->next;
greaterTail->next=NULL;
pHead=lessGuard->next;
free(greaterGuard);
free(lessGuard);
return pHead;
}
};
七.链表的回文结构
测试用例：
class PalindromeList {
public:
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;
}
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* n1,*n2,*n3;
n1=NULL;
n2=head;
n3=NULL;
while(n2)
{
n3=n2->next;
n2->next=n1;
//迭代
n1=n2;
n2=n3;
}
return n1;
}
bool chkPalindrome(ListNode* head)
{
//1.找中间结点
struct ListNode* mid=middleNode(head);
//2.逆序包括中间结点在内之后的结点
struct ListNode* rmid=reverseList(mid);
while(head&&rmid)
{
//判断回文
if(head->val!=rmid->val)
{
return false;
}
head=head->next;
rmid=rmid->next;
}
return true;
}
};
八.相交链表
1.思路：想找到俩链表相交的结点，即需要俩链表的最后一个结点的next指针域指向的结点地址相同；（注意而非val相同）
2.要求：时间复杂度为O(n+m),空间复杂度为O(1);
3.方法：（1）是否相交->俩链表的尾结点是否相等；
（2）求出俩链表的长度lenA，lenB
（3）较长的链表先走 差距步 ，然后再俩链表同时走，第一个结点地址相等，那就是链表交点。
（4）注意空链表无结点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* curA=headA;
struct ListNode* curB=headB;
int lenA=1;
int lenB=1;
//计算链表长度，找到尾结点
while(curA)
{
curA=curA->next;
lenA++;
}
while(curB)
{
curB=curB->next;
lenB++;
}
//如果俩链表遍历到最后的结点地址不相同
//则两链表不相交
if(curA!=curB)
{
return NULL;
}
struct ListNode* shorttail=headA;
struct ListNode*longtail=headB;
if(lenA>lenB)
{
shorttail=headB;
longtail=headA;
}
//先走差距步
int gap=abs(lenA-lenB);
while(gap--)
{
longtail=longtail->next;
}
while(longtail&&shorttail)//俩链表一起走的时候，保证不为空
{
if(longtail==shorttail)//相等时返回结点
{
return shorttail;
}
else
{
longtail=longtail->next;
shorttail=shorttail->next;
}
}
return NULL;
}
九.环形链表I
注意环形链表不能遍历
测试用例：
解题思路1：
方法：快慢指针
fast指针一次走两步，slow指针一次走一步
代码实现：
bool hasCycle(struct ListNode *head)
{
struct ListNode* fast,*slow;
//1.快慢指针指向头结点
fast=slow=head;
//2.追赶
//因为fast走的比slow快
//若有环则循环
//若无环fast会先指向NULL，跳出循环
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
//慢指针一次走一步
//快指针一次走两步
//走一次，差距缩小一步
//直到相遇
if(slow==fast)
{
return true;
}
}
return false;
}
思考问题1:
（1）请问，slow一次走一步，fast一次走三步，是否可以？
假设slow进环后，fast和slow之间差距N，那么追赶的距离就是N；
这种情况下，每追赶一次，他们之间的距离就缩小2步。·如果追赶的距离N是偶数，就追得上；
若N是奇数，意味着fast与slow，在第一次中，不会刚好相遇，会出现以下这种情况，于是他们之间的距离就变成了C-1(C是环的长度)，并进入新一轮的追赶，在这种情况下，若C-1是偶数，则这一轮追得上，若C-1是奇数，则永远追不上。
（2）请问，slow一次走一步，fast一次走X步，是否可以？
（3）请问，slow一次走Y步，fast一次走X步（X>Y）,是否可以？
与上面的情况同理，能否追赶上取决于，每追赶一次，slow和fast指针的距离是缩小偶数倍，还是奇数倍，并且取决于环的长度。
十.环形链表II
这道题与上道题大近相同，这道题要判断链表是否有环，还需要返回链表开始入环的第一个结点（即L的位置）,如果链表无环，则返回NULL。
解题思路1：公式推导
由上述环状链表可得，fast快指针一次走两步，slow一次走一步，所以得出公式：fast走的距离=2*slow走的距离。
（1）假设进环前的长度是L，环的长度是C，入口点到相遇点距离是X
（2）则slow走的距离是：L+X；fast走的距离是：L+N*C+X;（假设slow进环，fast在环里面已经转了N圈，N>=1）
（3）推导公式：
2(L+X)=L+NC+X
L+X=NC
L=NC-X
L=(N-1)C+C-X
可以这么说：一个指针A从头开始走，一个指针B从相遇点开始走，他们会在入口点相遇
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode* slow, *fast;
slow=fast=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 head;//or meet
}
}
return NULL;
}
解题思路2：转换成相交问题
1.找到交点(slow==fast);
2.保留链表交点下一个结点的地址
3.断开链表
4.找链表交点
5.恢复链表
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* curA=headA;
struct ListNode* curB=headB;
int lenA=1;
int lenB=1;
//计算链表长度，找到尾结点
while(curA)
{
curA=curA->next;
lenA++;
}
while(curB)
{
curB=curB->next;
lenB++;
}
//如果俩链表遍历到最后的结点地址不相同
//则两链表不相交
if(curA!=curB)
{
return NULL;
}
struct ListNode* shorttail=headA;
struct ListNode*longtail=headB;
if(lenA>lenB)
{
shorttail=headB;
longtail=headA;
}
//先走差距步
int gap=abs(lenA-lenB);
while(gap--)
{
longtail=longtail->next;
}
while(longtail&&shorttail)//俩链表一起走的时候，保证不为空
{
if(longtail==shorttail)//相等时返回结点
{
return shorttail;
}
else
{
longtail=longtail->next;
shorttail=shorttail->next;
}
}
return NULL;
}
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode* fast, *slow;
fast=slow=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(fast==slow)
{
//相遇点
struct ListNode* meet=slow;
//保存相遇点的下一个结点
struct ListNode* next=meet->next;
//断开环
meet->next=NULL;
//恢复环
struct ListNode* entryNode=getIntersectionNode(next,head);//找交点
meet->next=next;
return entryNode;
}
}
return NULL;
}