系列文章目录
前言
一、合并有序链表
1.题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
2.解题思路
- 取两个链表中值小的一个当为头节点
- 然后一直取两个链表中小的节点尾插到头节点后面
- 注意判断结束条件
代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l1;
}
struct ListNode* head=NULL,*tail=NULL;
if(l1->val<l2->val)
{
head=tail=l1;
l1=l1->next;
}
else
{
head=tail=l2;
l2=l2->next;
}
while(l1&&l2)
{
if(l1->val<l2->val)
{
tail->next=l1;
l1=l1->next;
}
else
{
tail->next=l2;
l2=l2->next;
}
tail=tail->next;
}
if(l1)
{
tail->next=l1;
}
if(l2)
{
tail->next=l2;
}
return head;
}
二、链表分割
1.题目描述
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
2.解题思路
- 把小于k值得链表分一个链表，大于k的值分为一个链表，最后把两个链表链接起来。
代码如下：
/*
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
//两个哨兵节点greatHead，lessHead
struct ListNode* lessHead=NULL,*lessTail=NULL;
struct ListNode* greatHead=NULL,*greatTail=NULL;
lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
greatHead=greatTail=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur=pHead;
while(cur)
{
if(cur->val<x)
{
lessTail->next=cur;
lessTail=lessTail->next;
}
else
{
greatTail->next=cur;
greatTail=greatTail->next;
}
cur=cur->next;
}
lessTail->next=greatHead->next;
greatTail->next=NULL;
pHead=lessHead->next;
free(lessHead);
free(greatHead);
return pHead;
}
};
三、链表回文结构
1.题目描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
2.解题思路
- 链表回文无非就是链表是否对称 ，可以先找链表的中间节点
- 把中间节点之后的节点逆置一遍
- 在把前面的节点值和链表后面的节点值相比较即可
代码如下：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
//1.先找中间节点
//逆置中间结点后面的结点
//头结点到中间结点前面一个和中间结点后面的结点值相比较
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode *fast=head,*slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
struct ListNode* reverse(struct ListNode* head)
{
struct ListNode* cur=head;
struct ListNode* newhead=NULL;
while(cur)
{
struct ListNode* next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}
bool chkPalindrome(ListNode* A)
{
struct ListNode* mid=middleNode(A);
struct ListNode* rhead=reverse(mid);
while(A&&rhead)
{
if(A->val!=rhead->val)
{
return false;
}
else
{
A=A->next;
rhead=rhead->next;
}
}
return true;
}
};
四、链表公共节点
1.题目描述
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
2.解题思路
- 遍历分别求出两个链表的长度
- 计算两个链表相差的长度
- 长的链表先走相差的长度
- 两个链表一起走
- 如果有节点的地址相同，则返回，否则没有
代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
#include<math.h>
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
if(headA==NULL||headB==NULL)
{
return NULL;
}
struct ListNode* curA=headA,*curB=headB;
int lenA=0;
int lenB=0;
while(curA->next)
{
lenA++;
curA=curA->next;
}
while(curB->next)
{
lenB++;
curB=curB->next;
}
if(curA!=curB)
{
return NULL;
}
struct ListNode* longList=headA,*shortList=headB;
if(lenB>lenA)
{
longList=headB;
shortList=headA;
}
int gap=abs(lenA-lenB);
while(gap--)
{
longList=longList->next;
}
while(longList!=shortList)
{
longList=longList->next;
shortList=shortList->next;
}
return longList;
}
总结
以上就是今天要讲的内容，本文仅仅简单介绍了链表几道经典题的解法，后面会继续发布链表后面的题目解法，希望大家多多支持。还有，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。
转载：https://blog.csdn.net/qq_44918090/article/details/116780753
查看评论