기술나눔

한어Русский язык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