目录
1.反转单链表206. 反转链表
2.有序链表合并21. 合并两个有序链表
3.链表分割（上一题的扩展）
4.相交链表160. 相交链表
5.环形链表142. 环形链表 II
6.复制带随机指针链表138. 复制带随机指针的链表
7.两两交换节点24. 两两交换链表中的节点
1.反转单链表206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//思路很简单，只需把头节点拿下来，再依次连接即可
代码实现
struct ListNode* reverseList(struct ListNode* head){
struct ListNode*newhead=NULL;
struct ListNode*cur=head;
struct ListNode*next=cur;
while(cur)
{
next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}
将两个有序链表合并为一个新的有序链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成 的。
思路：双指针进行遍历，每次比较两个链表中值的大小，将更小的节点取下，再依次进行连接。
代码实现：
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,分贝指向合并后链表的头尾
tail=head=NULL;
while(list1&&list2)
{
if(list1->valval)
{
if(tail==NULL)
{
head=tail=list1;//刚开始时，将head，tail都置为值最小的节点
}
else
{
tail->next=list1;//后依次比较，进行连接
tail=list1;
}
list1=list1->next;//值较小的链表往前遍历
}
else
{
if(tail==NULL)
{
head=tail=list2;//刚开始时，将head，tail都置为值最小的节点
}
else
{
tail->next=list2;//后依次比较，进行连接
tail=list2;
}
list2=list2->next;//值较小的链表往前遍历m
}
}
if(list1)
{
tail->next=list1;//此时list1还存在一个节点未遍历，将其合并在新链表后面
}
if(list2)
{
tail->next=list2;//此时list2还存在一个节点未遍历，将其合并在新链表后面
}
return head;
} 现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于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*p1,*p2,*p11,*p22;
//p1为链表(该链表中的值小于x)的头节点，p11为该链表的尾节点
//p2为链表(该链表中的值大于x)的头节点，p22为该链表的尾节点
p1=p2=p22=p11=NULL;
while(pHead)
{
if(pHead->valnext=pHead;//依次把next=pHead;//依次把>x的链表连接
p22=pHead;//更新尾节点
}
}
pHead=pHead->next;//比较完一个节点，往后遍历
}
if(p1==NULL)//p1为空，指原节点所有的值指都大于x，返回p2
{
return p2;
}
p11->next=p2;//此时p1不为空，将p11连接在p2上，进行链表合并
if(p2!=NULL)
{
p22->next=NULL;//将p22尾节点指向空
}
return p1;
}
};
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
如果两个链表不存在相交节点，返回 null 。
思路：用两个指针分别指向两个链表的头节点，进行遍历，找到节点的个数。
后让节点数更多的链表先遍历步，再同时遍历，若可以找到相同的节点，既是相交节点。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode*p1,*p2;
p1=headA;//记录A节点起始位置
p2=headB;//记录B节点起始位置
int A=1;//记录A链表节点的个数
int B=1;//记录B链表节点的个数
while(headA->next)
{
headA=headA->next;
A++;
}
while(headB->next)
{
headB=headB->next;
B++;
}
if(headA!=headB)
{
return NULL;
}
//让节点更多的链表先走
if(A>B)
{
int k=A-B;
while(k--)
{
p1=p1->next;
}
}
else
{ int k=B-A;
while(k--)
{
p2=p2->next;
}
}
while(p1!=p2)//两个链表再同时遍历，若遇到相同节点即使是相交。
{
p1=p1->next;
p2=p2->next;
}
if(p1==p2)
{
return p1;
}
return NULL;
}
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。
如果链表无环，则返回 null。
思路：快慢指针法（fast一次遍历两个节点，slow一次遍历一个节点）
解法1：
slow走的距离：L+x；fast走的距离L+n*C+x，且slow走的距离是fast所走距离的一半
2*（L+x）=L+n*C+x；即：L=n*C-x；所以一个指针从起始位置开始走，另一个指针从相交点开始走，它们定会在入口点相遇。
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*fast,*slow;
fast=slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)//找到相遇点
{
struct ListNode *meet=slow;
while(meet!=head)
{
meet=meet->next;
head=head->next;
}
return head;
}
}
return NULL;
};解法2：（参照例题4）
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*fast,*slow;
fast=slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
break;
}
}
if(fast==NULL||fast->next==NULL)
{
return NULL;
}
struct ListNode*meet=slow;
struct ListNode*newhead=meet->next;
meet->next=NULL;
struct ListNode*p1,*p2;
p1=head;
p2=newhead;
int A=1;
int B=1;
while(p1->next)
{
p1=p1->next;
A++;
}
while(p2->next)
{
p2=p2->next;
B++;
}
struct ListNode*lonp=head,*shorp=newhead;
int gas=abs(A-B);
if(B>A)
{
lonp=newhead;
shorp=head;
}
while(gas--)
{
lonp=lonp->next;
}
while(lonp&&shorp)
{
if(lonp==shorp)
{
return lonp;
}
lonp=lonp->next;
shorp=shorp->next;
}
return NULL;
}给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。
深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。
新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。
复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。
那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
思路 1.先将拷贝节点连接在原节点的后面
2.链接拷贝节点的random指针（拷贝节点的random在原节点random后面）
3.将拷贝节点解下来，连接在一起
struct Node* copyRandomList(struct Node* head)
{
struct Node* cur = head;
while(cur)//先将拷贝节点连接在原节点的后面
{
struct Node* next = cur->next;
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->val = cur->val;
cur->next = copy;
copy->next = next;
cur = next;
}
cur = head;
while(cur)//链接拷贝节点的random指针（拷贝节点的random接在原节点random后面）
{
struct Node* copy = cur->next;
if(cur->random != NULL)
copy->random = cur->random->next;
else
copy->random = NULL;
cur = copy->next;
}
1
struct Node* copyHead = NULL, *copyTail = NULL;
cur = head;
while(cur)//将拷贝节点解下来，连接在一起
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
// copy解下来尾插
if(copyTail == NULL)
{
copyHead = copyTail = copy;
}
else
{
copyTail->next = copy;
copyTail = copy;
}
cur->next = next;
cur = next;
}
return copyHead;
};
2
struct Node* copyHead = NULL;//将拷贝节点解下来，连接在一起
struct Node* newhead,*next;
newhead=next=NULL;
cur = head;
copyHead=cur->next;
while(cur)
{
newhead=cur->next;
next=newhead->next;
cur->next=next;
if(next!=NULL)
{
newhead->next=next->next;
}
else
{
newhead->next=NULL;
}
cur=next;
}
return copyHead;
}；
你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路：定义一个指针，指向头节点，确保其连续的两个节点不为空，在对其进行交换
struct ListNode* swapPairs(struct ListNode* head){
struct ListNode*newhead=NULL;
if(head==NULL||head->next==NULL)
{
return head;
}
newhead=head->next;//保留头节点
struct ListNode*prev=(struct ListNode*)malloc(sizeof(struct ListNode));
prev->next=head;
while(prev->next&&prev->next->next)//交换
{
struct ListNode*p1=prev->next;
struct ListNode*p2=p1->next;
prev->next=p2;
p1->next=p2->next;
p2->next=p1;
prev=p1;
}
return newhead;
}欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）