🍉博客主页：阿博历练记
📖文章专栏：数据结构与算法
🔍代码仓库：阿博编程日记
🌹欢迎关注：欢迎友友们点赞收藏+关注哦

🖋1.题目描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

💡 逻辑分析

📃哨兵位的概念

哨兵位的头结点不存储有效数据，是一个附加的链表节点，该节点作为第一个节点,它的值域不存储任何东西.只是为了操作的方便而引入的，如果一个链表有哨兵节点的话,那么线性表的第一个元素应该是链表的第二个节点.

❌错误案例(不带哨兵位）

#include <cstddef>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct  ListNode*lesshead=NULL,*lesstail=NULL,*graterhead=NULL,*gratertail=NULL;
        struct  ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
               if(lesstail==NULL)
               {
                 lesshead=lesstail=cur;
               }
               else 
               {
                  lesstail->next=cur;
                  lesstail=lesstail->next;
               }
            }
            else
            {
               if(gratertail==NULL)
               {
                graterhead=gratertail=cur;
               }
               else 
               {
                 gratertail->next=cur;
                 gratertail=gratertail->next;
               }
            }
            cur=cur->next;
        }
        lesstail->next=graterhead;
        return    lesshead;
 }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

✔代码纠正

1.不带哨兵位

#include <cstddef>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct  ListNode*lesshead=NULL,*lesstail=NULL,*graterhead=NULL,*gratertail=NULL;
        struct  ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
               if(lesstail==NULL)
               {
                 lesshead=lesstail=cur;
               }
               else 
               {
                  lesstail->next=cur;
                  lesstail=lesstail->next;
               }
            }
            else
            {
               if(gratertail==NULL)
               {
                graterhead=gratertail=cur;
               }
               else 
               {
                 gratertail->next=cur;
                 gratertail=gratertail->next;
               }
            }
            cur=cur->next;
        }
        if(lesstail==NULL)
        return   graterhead;
        else
        {
        lesstail->next=graterhead;
        if(gratertail)
        gratertail->next=NULL;
        return    lesshead;
        }
 }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

2.带哨兵位

#include <cstddef>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct  ListNode*lesshead,*lesstail,*graterhead,*gratertail;
        lesshead=lesstail=(struct  ListNode*)malloc(sizeof(struct ListNode));
        graterhead=gratertail=(struct  ListNode*)malloc(sizeof(struct ListNode));
        struct  ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                  lesstail->next=cur;
                  lesstail=lesstail->next;
            }
            else
            {
                 gratertail->next=cur;
                 gratertail=gratertail->next;
            }
            cur=cur->next;
        }
        lesstail->next=graterhead->next;
        gratertail->next=NULL;
        pHead=lesshead->next;
        free(lesshead);
        free(graterhead);
        return  pHead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

友友们注意了，当我们用完哨兵位之后，我们要及时把它释放掉，返回链表新的头结点

🖋2.题目描述

📒 回文链表的概念(逻辑实现）

回文结构特征是正着读和反着读是一样的，因此我们只要找到链表的中间结点，再将链表的后半部分逆置，使用两个指针分别从头和中间结点开始遍历，如果在他们的next为空之前一直相等，说明该链表为回文结构。

⭐疑问解析

🏆代码展示

class PalindromeList {
public:
 struct ListNode* reverseList(struct ListNode* head){
     struct  ListNode*cur=head;
     if(cur==NULL)
     {
         return  NULL;
     }
     struct  ListNode*rhead=NULL;
     struct  ListNode*next=cur->next;
     while(cur)
     {
     cur->next=rhead;
         rhead=cur;
         cur=next;
         if(cur)
         {
         next=cur->next;
         }
     }
     return  rhead;
}
struct ListNode* middleNode(struct ListNode* head){
     struct  ListNode*slow=head;
     struct  ListNode*fast=head;
     while(fast&&fast->next)
     {
         fast=fast->next->next;
         slow=slow->next;
     }
     return  slow;
}
bool chkPalindrome(ListNode* head){
     struct  ListNode*mid=middleNode(head);
     struct  ListNode*rmid=reverseList(mid);
     while(rmid)
     {
     if(rmid->val!=head->val)
        {
        return  false;
        }
        head=head->next;
        rmid=rmid->next;
     }
     return  true;
 }
 };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

🖋3.题目描述

💡 逻辑分析

我们先求出链表A和链表B的长度L1和L2，使用双指针，并将他们对齐，即若A链表节点比B节点多n个，则将A的指针向后移动n个，B链表比A链表多时同理.保证剩余链表长度相同，然后在一起走，两个指针同步向后移动1个节点，要么同时找到第一个交点，要么都为NULL.

🏆代码展示

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int t1=0;
    int t2=0;
    struct  ListNode*p1=headA;
    struct  ListNode*p2=headB;
    if(p1==NULL||p2==NULL)
    return  NULL;
    while(p1)
    {
        t1++;
        p1=p1->next;
    }
    p1=headA;
    while(p2)
    {
        t2++;
        p2=p2->next;
    }
    p2=headB;
    if(t1>t2)
    {
    int temp=t1-t2;
       while(temp)
       {
           p1=p1->next;
           temp--;
       }
    }
    else
    {
        int  temp=t2-t1;
        while(temp)
        {
            p2=p2->next;
            temp--;
        }
    }
    while(p1&&p1!=p2)
    {
        p1=p1->next;
        p2=p2->next;
    }
    return  p1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44