重生之“我打数据结构，真的假的？”--2.单链表

1.单链表介绍（不带头节点）

1.1.链表的概念

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，但链表在逻辑上是连续的，顺序的，而数据元素的逻辑顺序是通过链表中的指针连接次序实现的。

1.2.链表的结构

typedef struct SListnode
{
	datatype data;
	struct SListnode* next;
}SLnode;

2.力扣习题 

2.1——返回倒数第k个节点

. - 力扣（LeetCode）

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——对链表进行插入排序

. - 力扣（LeetCode）

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。（我使用的是原地算法，不用再malloc一个链表指针，不过比较麻烦（可恶））
3. 重复直到所有输入数据插入完为止。

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;
    }
};