Technology Sharing

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

LeetCode 027. How to write a palindrome list in C

思路🧐：

​ Fast and slow pointer+Reversing a linked list, find the middle node through the fast and slow pointers, and then reverse all the nodes after the middle node. If it is a palindrome linked list, then the values ​​after the middle node are equal to the values ​​from the head node to the middle node. If there are any inequalities, it is not a palindrome linked list.

Code ✨:

 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