leetCode-0234_回文链表

Posted on | In |

题目描述

Given a singly linked list, determine if it is a palindrome.

Example 1:

1
2
Input: 1->2
Output: false

Example 2:

1
2
Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

中文题目

请判断一个链表是否为回文链表。

示例 1:

1
2
输入: 1->2
输出: false

示例 2:

1
2
输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解决方法

方法一
  • 描述
  1. 使用快慢指针，快指针每次前进两步，慢指针每次前进一步，慢指针走的过程中，同时修改next指针，使得前半部分逆序。会形成一个指向前半部分逆序的指针prev和一个指向后半部分的指针slow
  2. 每次同时移动prev和slow一个指针，如有某个节点不相等，则非回文，反之回文
  • 源码
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
48
49
50
51
52
53
54
55
56
57
58
/**
 回文链表
 
 @param head 不带头结点
 @return 是否回文链表
 */
bool isPalindrome(struct ListNode *head)
{
    if (head == NULL || head->next == NULL) {
        return true;
    }
    
    struct ListNode *fast = head;
    struct ListNode *slow = head;
    struct ListNode *prev = NULL;
    
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        
        //逆转前部分
        struct ListNode *temp = slow->next;
        slow->next = prev;
        prev = slow;
        slow = temp;
    }
    
    if (fast != NULL) {
        slow = slow->next;
    }
    
    while (slow != NULL) {
        if (prev->val != slow->val) {
            return false;
        }
        slow = slow->next;
        prev = prev->next;
    }
    
    return true;
}


/**
 回文链表
 */
void isPalindrome_test()
{
    SingleLinkListNode *head = single_link_list_create();
    single_link_list_insert_tail(head, 1);
    single_link_list_insert_tail(head, 2);
    single_link_list_insert_tail(head, 2);
    single_link_list_insert_tail(head, 1);
    
    printf("========回文链表========\n");
    single_link_list_dump_head(head);
    bool flag = isPalindrome(head->next);
    printf("是否回文:1回文，0非回文 => %d\n",flag);
}

题目来源

Palindrome Linked List
回文链表

线性表相关代码

数据结构-线性表