Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

LeetCode 027. Πώς να γράψετε μια συνδεδεμένη λίστα με παλίνδρομο στο C

思路🧐：

​ δείκτη ταχύτητας+Αντίστροφη συνδεδεμένη λίστα , βρείτε τον ενδιάμεσο κόμβο μέσα από τους γρήγορους και αργούς δείκτες και, στη συνέχεια, αντιστρέψτε όλους τους κόμβους μετά τον ενδιάμεσο κόμβο. Εάν πρόκειται για λίστα συνδεδεμένη με παλίνδρομο, τότε οι τιμές από τον ενδιάμεσο κόμβο στον ενδιάμεσο κόμβο είναι ίσες με τις τιμές από τον κεντρικό κόμβο στον ενδιάμεσο κόμβο, εάν υπάρχουν άνισες τιμές, δεν είναι συνδεδεμένη λίστα με παλίνδρομο .

Κωδικός ✨:

 struct ListNode* MidNode(struct ListNode* head) //找中间结点
 {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
 }
 struct ListNode* Reverse(struct ListNode* midhead) //链表反转
 {
    struct ListNode* rhead = NULL;
    struct ListNode* cur = midhead;
    while(cur)
    {
        struct ListNode* tail = cur->next;
        cur->next = rhead;
        rhead = cur;
        cur = tail;
    }
    return rhead;
 }


bool isPalindrome(struct ListNode* head){
    struct ListNode* cur = head;
    struct ListNode* mid = MidNode(head);
    struct ListNode* midhead = Reverse(mid);
    while(cur != mid) //当cur走到mid结点处就结束
    {
        if(cur->val != midhead->val) //如果不相等就返回false
        {
            return false;
        }
        else //如果相等就继续往后走
        {
            cur = cur->next;
            midhead = midhead->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