- 反转链表
- 解题思路
- 代码
- 链表的中间结点
- 解题思路
- 代码
- 移除链表元素
- 解题思路
- 代码
- 链表中倒数第k个结点
- 解题思路
- 代码
- 合并两个有序链表
- 解题思路
- 代码
- 链表分割
- 解题思路
- 代码
- 链表的回文结构
- 解题思路
- 代码
- 相交链表
- 解题思路
- 代码
- 环形链表1
- 解题思路
- 代码
- 环形链表2
- 解题思路
- 代码
- 复制带随机指针的链表
- 解题思路
- 代码
反转链表 解题思路
指针反转法
这里我们直接把节点的指针进行反转就行，反转的时候要注意保存好下一个节点的地址和上一个节点的地址。
n1表示当前节点的上一个节点的地址
n2表示当前节点
n3表示当期节点的下一个节点的地址
节点插入法
我们创建新的头节点的地址，原链表中的每个节点一个一个进行头插。
指针反转法
struct ListNode* reverseList(struct ListNode* head){
if(head==NULL)
return head;
struct ListNode* n1,*n2,*n3;
n1=NULL;
n2=head;
n3=head->next;
while(n3)
{
n2->next=n1;
n1=n2;
n2=n3;
n3=n2->next;
}
n2->next=n1;
return n2;
}
节点插入法
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* newhead=NULL;
while(head)
{
struct ListNode* cur=head;
head=head->next;
cur->next=newhead;
newhead=cur;
}
return newhead;
}
代码快慢指针法，慢指针走一步，快指针走两步。当快指针指向为空的时候。慢指针指向的节点即为中间的节点。
struct ListNode* middleNode(struct ListNode* head){
struct ListNode *low,*quick;
low=head;
quick=head;
while(quick->next)
{
low=low->next;
quick=quick->next;
if(quick==NULL)
break;
quick=quick->next;
if(quick==NULL)
break;
}
return low;
}
方法1：遍历链表，遇到val，则跳过该节点。
代码方法1：
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode* cur=head;
struct ListNode* curpro=head;
while(head&&head->val==val)
{
head=head->next;
free(cur);
cur=head;
}
while(cur)
{
if(cur->val==val)
{
curpro->next=cur->next;
free(cur);
cur=curpro->next;
}
else{
curpro=cur;
cur=curpro->next;
}
}
return head;
}
快慢指针法，先让快指针走k步，然后快慢指针一起走。直到快指针为空的时候，慢指针指向的节点就是倒数第k个节点。
注意k的值大于节点个数的时候，返回的为空。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
struct ListNode *slow,*quick;
slow=NULL;
quick=pListHead;
int i=0;
while(i<k&&quick)
{
quick=quick->next;
i++;
}
if(i==k)
{
slow=pListHead;
while(quick)
{
slow=slow->next;
quick=quick->next;
}
}
return slow;
}
开辟一个头节点用于当中新的链表，里面不存有效值，对应给的两个链表，从首个节点开始进行val值的比较，小的那个值的节点插入到新的节点的后面，一直到某个链表节点的结尾。把剩下一个链表的全部插入到新链表的后面。最后不要忘记释放头节点。
代码struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur=newhead;
while(list1&&list2)
{
if(list1->val<list2->val)
{
cur->next=list1;
list1=list1->next;
cur=cur->next;
}
else
{
cur->next=list2;
list2=list2->next;
cur=cur->next;
}
}
if(list1==NULL)
{
cur->next=list2;
}
else{
cur->next=list1;
}
//销毁
cur=newhead->next;
free(newhead);
newhead=NULL;
return cur;
}
解题思路题目的意思是这样的,小于x的节点在前面，大于等于x的节点排在后面，其相对位置不变。看下面的更能更好的理解。
我们把原链表分成2个链表，第一个链表为小于x的链表，第二个链表为大于等于x的链表。最后第二个链表连接到第一个链表的后面。返回第一个链表的地址。
形成两个链表的过程中，遍历原链表。两个链表都是带头节点的。
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode *list1=(struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode *list2=(struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode *head1,*head2,*tail1,*tail2;
list1->next=NULL;
list2->next=NULL;
head1=tail1=list1;
head2=tail2=list2;
while(pHead)
{
if(pHead->val<x)
{
tail1->next=pHead;
pHead=pHead->next;
tail1=tail1->next;
}
else
{
tail2->next=pHead;
pHead=pHead->next;
tail2=tail2->next;
}
}
tail2->next=NULL;
tail1->next=head2->next;
struct ListNode *head=head1->next;
free(list1);
free(list2);
return head;
}
};
另一种写法
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode *head1,*head2,*tail1,*tail2;
head1=tail1=head2=tail2=NULL;
while(pHead)
{
if(pHead->val<x)
{
if(tail1==NULL)
{
head1=tail1=pHead;
}
else
{
tail1->next=pHead;
tail1=tail1->next;
}
}
else
{
if(tail2==NULL)
{
head2=tail2=pHead;
}
else
{
tail2->next=pHead;
tail2=tail2->next;
}
}
pHead=pHead->next;
}
if (head1 == NULL)
return head2;
if (head2 == NULL)
return head1;
tail2->next=NULL;
tail1->next=head2;
struct ListNode *head=head1;
return head;
}
};
1.找到中间节点，然后把中间节点后面的节点进行逆序
2.没有逆序的部分与逆序的部分进行比较，相同即为回文，否则不是回文。
3.是回文结束的标准为节点为空。
4.恢复破坏的链表结构
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode *slow,*quick;
slow=quick=head;
while(head&&head->next)
{
slow=slow->next;
head=head->next->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
if(head==NULL)
return NULL;
struct ListNode *n1,*n2,*n3;
n1=NULL;
n2=head;
n3=head->next;
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
n3=n3->next;
}
struct ListNode* newhead=n1;
return newhead;
}
bool isPalindrome(struct ListNode* head){
struct ListNode* mid= middleNode(head);
mid=reverseList(mid);
struct ListNode* temp=mid;
struct ListNode* cur=head;
while(cur&&mid)
{
if(cur->val!=mid->val)
{
reverseList(temp);
return false;
}
else
{
cur=cur->next;
mid=mid->next;
}
}
reverseList(temp);
return true;
}
1.先求出两个链表的长度，求出它们的差值。
2.让长的链表先走差值步。
3.然后两人链表同时走，发现有地址相同的时候就返回该地址的节点。没有就返回空。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *curA=headA,*curB=headB;
int lenA=0,lenB=0;
while(curA)
{
curA=curA->next;
lenA++;
}
while(curB)
{
curB=curB->next;
lenB++;
}
struct ListNode *shorts=headA,*longs=headB;
if(lenA>lenB)
{
shorts=headB;
longs=headA;
}
int k=lenA>lenB?lenA-lenB:lenB-lenA;
while(k--)
{
longs=longs->next;
}
while(shorts&&longs)
{
if(shorts==longs)
return shorts;
else
{
shorts=shorts->next;
longs=longs->next;
}
}
return NULL;
}
本题用快慢指针进行解决，快指针走2步，慢指针走一步。当两个指针相等时即存在环。
代码bool hasCycle(struct ListNode *head) {
struct ListNode *slow,*quick;
slow=quick=head;
while(quick&&quick->next)
{
slow=slow->next;
quick=quick->next->next;
if(slow==quick)
return true;
}
return false;
}
思路1：
先用快慢指针找到他俩相遇的节点，然后一个从头开始走，一个从相遇点开始走，当它们相遇的时候即为环的第一个节点。
证明
假设不是环的长度为L，环的长度为C。这里L表达节点的个数。
快指针一次走两步，慢指针一次走一步，当慢指针开始进入环的时候，快指针走了L+N*C+Y（N表示整数，Y表示不足1圈的步数），慢指针走了L。
这时，慢指针和快指针开始了追击。当快，慢指针相遇的时候。假设慢指针在环中走了X步，快指针走了C-Y+X步。
慢指针：L+X
快指针：L+(N+1) * C+X
由快慢指针的关系：
2(L+X)=L+(N+1) * C+X =>L=(N+1)*C-X=> L=N * C+(C-X)
L=N * C+(C-X)
从这个表达式中可以看出来一个指针从头开始走，另一个从相遇点开始走，相遇时就是环的第一个节点。
思路2：
同样需要快慢指针，当快慢指针相遇的时候，把该节点制成空。这时题目就变成找两个链表的相交节点。注意： 最后要把破坏的链表恢复到原来的模样。
思路1：
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *slow,*quick;
slow=quick=head;
while(quick&&quick->next)
{
slow=slow->next;
quick=quick->next->next;
if(slow==quick)
{
struct ListNode* cur=head;
while(cur!=slow)
{
cur=cur->next;
slow=slow->next;
}
return cur;
}
}
return NULL;
}
思路2：
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *slow,*quick;
int L1,L2;
L1=L2=0;
slow=quick=head;
while(quick&&quick->next)
{
slow=slow->next;
quick=quick->next->next;
if(slow==quick)
{
struct ListNode*cur=head;
struct ListNode* newhead=slow->next;
slow=slow->next;
quick->next=NULL;
while(cur)
{
cur=cur->next;
L1++;
}
while(slow)
{
slow=slow->next;
L2++;
}
int divalue=L1>L2?L1-L2:L2-L1;
struct ListNode *shorts=head,*longs=newhead;
if(L1>L2)
{
shorts=newhead;
longs=head;
}
while(divalue--)
longs=longs->next;
while(shorts!=longs)
{
shorts=shorts->next;
longs=longs->next;
}
quick->next=newhead;
return shorts;
}
}
return NULL;
}
1.原链表每个节点后面插入一个和它一样的节点。
新的链表就是插入的节点（还没有链接在一起）
2.复制节点中random指向的节点 == 原节点中random指向的节点的后一个节点。从上图中可以看出来。
3.恢复原链表，剪除新链表。
先让原链表中的节点指向新链表节点的下一个节点，原链表节点移动一位。
然后新链表中的节点指向原链表节点的下一个节点。一次遍历就行。
struct Node* copyRandomList(struct Node* head) {
struct Node* cur=head;
while(cur)
{
struct Node *newnode=(struct Node*)malloc(sizeof(struct Node));
newnode->val=cur->val;
//插进去
newnode->next=cur->next;
cur->next=newnode;
cur=newnode->next;
}
//random 指向恢复
cur=head;
while(cur)
{
struct Node* curnext=cur->next;
if(cur->random==NULL)
curnext->random=NULL;
else
curnext->random=cur->random->next;
cur=curnext->next;
}
//恢复原链表，新成新链表
cur=head;
struct Node *newhead=NULL,*newtail=NULL;
while(cur)
{
if(newtail==NULL)
newhead=newtail=cur->next;
cur->next=newtail->next;
cur=cur->next;
if(cur)
newtail->next=cur->next;
newtail=newtail->next;
}
return newhead;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）