重生之“我打数据结构，真的假的？”--2.单链表
1.单链表介绍（不带头节点）
1.1.链表的概念
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，但链表在逻辑上是连续的，顺序的，而数据元素的逻辑顺序是通过链表中的指针连接次序实现的。
1.2.链表的结构
typedef struct SListnode
{
datatype data;
struct SListnode* next;
}SLnode;
2.力扣习题
2.1——返回倒数第k个节点
1.设定两个指针p，q指向头节点； 2.p先移动k次； 3.p，q一起 移动，直至p->next==NULL; 返回q；
int kthToLast(struct ListNode* head, int k){
struct ListNode* p=head;
struct ListNode* q=head;
int i=k;
for(i=0;i<k;i++)
p=p->next;
while(p!=NULL)
{
p=p->next;
q=q->next;
}
return q->val;
}2.2——链表的回文结构
1.设定两个指针，fast，slow； 2.在while（fast->next!=NULL&&fast->next->next!=NULL）下 fast走两步，slow走一步； 当循环停止时，slow为中间节点； 以测试样例为例：1->2->2->1 slow指向第一个2； 3.slow->next之后的节点，依次前插至slow->next之前； 1->2->1->2 4.slow=slow->next;指向1； fast=head；指向头； 5.在slow指向NULL前 如果fast->data一直==slow->data; 则为回文结构；
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
struct ListNode* fast=A;
struct ListNode* slow=A;
struct ListNode* flag=NULL;
struct ListNode* arr=NULL;
struct ListNode* q=NULL;
struct ListNode* w=NULL;
if(A->next==NULL)
return true;
while(fast->next!=NULL&&fast->next->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
}
flag=slow->next;
arr=flag->next;
//q=arr->next;
while(arr)
{
w=slow->next;
q=arr->next;
arr->next=NULL;
slow->next=arr;
arr->next=w;
flag->next=q;
arr=q;
}
fast=A;
slow=slow->next;
while(slow)
{
if(fast->val!=slow->val)
return false;
fast=fast->next;
slow=slow->next;
}
return true;
}
};2.3——对链表进行插入排序
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。（我使用的是原地算法，不用再malloc一个链表指针，不过比较麻烦（可恶））
- 重复直到所有输入数据插入完为止。
struct ListNode* insertionSortList(struct ListNode* head) {
struct ListNode* p;
struct ListNode* w;
struct ListNode* q;
struct ListNode* end=head;
struct ListNode* flag;
struct ListNode* t;
p=head;
q=p->next;
while(q)
{
if(q->val<end->val)
{
w=q->next;
end->next=q->next;
flag=p;
for(flag=p;((flag->val)<q->val)&&flag!=end;flag=flag->next);
if (flag == p)
{
q->next = flag;
}
else
{
t = head;
while (t->next != flag)
t = t->next;
q->next = flag;
t->next = q;
}
if(q->next==head)
{
head=q;
p=head;
}
q=w;
}
else
{
end=end->next;
q=q->next;
}
}
return head;
}3.错题反思
链表分割
1.原本想设定一个指针数组，记录所有小于x的节点地址； 然后依次连接；不知为何不行； 答案思路： 1.建立两个链表，要带有哨兵位！！！！
greatHead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));greattail用来移动和插入大于x的节点地址，greatHead用来记录头位置（greatHead->next是第一个节点）2.同理，另一个链表记录小于x的节点，最后两者连接一下就ok力；（lesstail->next = greatHead->next; //链接less链表和geart链表greattail->next = NULL; //注意处理最后一个节点的原链接关系）
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
//大体思路：创建两个链表，一个存储小于x的值，一个存储大于x的值，遍历原链表进行尾插。
//创建哨兵卫
struct ListNode* greatHead, *greattail, *lessHead, *lesstail, *cur;
greatHead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));
lessHead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
cur = pHead;
//遍历原链表进行尾插
while(cur)
{
if(cur->val < x)
{
lesstail->next = cur; //链接原链表头节点
lesstail = cur; //更新less链表尾节点
cur = cur->next; //原链表中cur继续更新往下走
}
else
{
greattail->next = cur;
greattail = cur;
cur = cur->next;
}
}
lesstail->next = greatHead->next; //链接less链表和geart链表
greattail->next = NULL; //注意处理最后一个节点的原链接关系
return lessHead->next;
}
};腾讯云开发者
