首页 回文
文章
取消

回文

发表于 2020/11/03
作者
11 分钟阅读

回文是指从左往右读，与从右往左读结果是一样的一种结构。

检测回文字符串

字符串其实就是一个字符数组。

平分检测

平分两段，然后其中一段翻转过来，与另一段进行比较。若相同则是回文字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def check_palindrome(text: str) -> bool:
    l = len(text)
    if l < 2:
        return True
    if l % 2 == 0:
        # 偶数长
        return text[:l // 2] == text[l // 2:][::-1]
    # 奇数长
    return text[:l // 2] == text[l // 2 + 1:][::-1]


if __name__ == '__main__':
    s1 = "abcdedcba"
    s2 = "abcddcba"
    s3 = "abcd"
    print(check_palindrome(s1))  # True
    print(check_palindrome(s2))  # True
    print(check_palindrome(s3))  # False

双指针夹逼

从两侧依次往中间比较，每对字符都一样才是回文字符串，有一对不一样肯定不是回文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def check_palindrome(text: str) -> bool:
    l = len(text)
    if l < 2:
        return True
    left, right = 0, l - 1
    while left < right:
        if text[left] != text[right]:
            # 只要有一个字符不等，则肯定不是回文
            return False
        # 往中间夹逼
        left += 1
        right -= 1
    return True


if __name__ == '__main__':
    s1 = "abcdedcba"
    s2 = "abcddcba"
    s3 = "abcd"
    print(check_palindrome(s1)) # True
    print(check_palindrome(s2)) # True
    print(check_palindrome(s3)) # False

由于 Python 的 list 支持负索引，所以我们也可以不用双指针：

1
2
3
4
5
6
7
8
9
10

def check_reverse(text: str) -> bool:
    l = len(text)
    if l < 2:
        return True
    half = l // 2
    for i in range(half):
        if text[i] != text[-i - 1]:
            # 只要有一个字符不等，则肯定不是回文
            return False
    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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

package main

import "fmt"

type DoubleNode struct {
	data int
	pre  *DoubleNode
	next *DoubleNode
}

type DoubleLinkedList struct {
	head *DoubleNode
	tail *DoubleNode
}

func (list *DoubleLinkedList) init(data ...int) {
	list.head = nil
	list.tail = nil

	for _, d := range data {

		if list.head == nil {
			doubleNode := DoubleNode{
				data: d,
				pre:  nil,
				next: nil,
			}

			list.head = &doubleNode
			list.tail = &doubleNode
		} else {
			doubleNode := DoubleNode{
				data: d,
				pre:  list.tail,
				next: nil,
			}
			list.tail.next = &doubleNode
			list.tail = &doubleNode
		}
	}
}

// 判断是否为空
func (list *DoubleLinkedList) empty() bool {
	return list.head == nil
}

// 添加1个元素
func (list *DoubleLinkedList) append(data int) {
	if list.head == nil {
		// 没有头部
		doubleNode := DoubleNode{
			data: data,
			pre:  nil,
			next: nil,
		}
		list.head = &doubleNode
		list.tail = &doubleNode
	} else {
		// 有头部
		doubleNode := DoubleNode{
			data: data,
			pre:  list.tail,
			next: nil,
		}
		list.tail.next = &doubleNode
		list.tail = &doubleNode
	}
}

// 添加多个元素
func (list *DoubleLinkedList) appendMany(data ...int) {
	for _, d := range data {

		if list.head == nil {
			doubleNode := DoubleNode{
				data: d,
				pre:  nil,
				next: nil,
			}

			list.head = &doubleNode
			list.tail = &doubleNode
		} else {
			doubleNode := DoubleNode{
				data: d,
				pre:  list.tail,
				next: nil,
			}
			list.tail.next = &doubleNode
			list.tail = &doubleNode
		}
	}
}

func (list *DoubleLinkedList) show() []int {
	if list.empty() {
		// 空链表
		return []int{}
	}
	var result []int
	p := list.head
	for p != nil {
		result = append(result, p.data)
		p = p.next
	}

	return result
}

func checkPalindrome(list *DoubleLinkedList) bool {
	if list.empty() {
		return true
	}
	lPre, l, r := list.head.pre, list.head, list.tail
	// 两边夹逼交汇的时候，有2种情况：
	// 1. 链表长度为奇数，l=r，两者都指向了中间的节点
	// 2. 链表长度为偶数，l=r.next，r=l.pre，两者在彼此的后方
	// 这2种情况下要停止夹逼
	for l != r && lPre != r {
		if l.data != r.data {
			return false
		}
		// l 往右移动
		l = l.next
		// l 的小跟班也往右走
		lPre = l.pre
		// r 往左走
		r = r.pre
	}
	return true
}

func main() {
	var list DoubleLinkedList
	list.init(2)
	fmt.Printf("%v, %v \n", list.show(), checkPalindrome(&list))

	list.appendMany(5, 8, 8, 5, 2)

	fmt.Printf("%v, %v \n", list.show(), checkPalindrome(&list))
	list.append(2)
	fmt.Printf("%v, %v \n", list.show(), checkPalindrome(&list))

	var list2 DoubleLinkedList
	list2.init(2, 5, 8, 5, 2)
	fmt.Printf("%v, %v \n", list2.show(), checkPalindrome(&list2))
}

输出结果：

1
2
3
4

[2], true
[2 5 8 8 5 2], true
[2 5 8 8 5 2 2], false
[2 5 8 5 2], 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
48
49

type Node struct {
	data int
	next *Node
}

type LinkedList struct {
	head *Node
	tail *Node
}

func (list *LinkedList) init() {
	(*list).head = nil
	(*list).tail = nil
}

func (list *LinkedList) empty() bool {
	return (*list).head == nil
}

func (list *LinkedList) appendMany(data ...int) {
	for _, d := range data {
		node := Node{
			data: d,
			next: nil,
		}
		if (*list).head == nil {
			(*list).head = &node
			(*list).tail = &node
		} else {
			(*list).tail.next = &node
			(*list).tail = &node
		}
	}
}

func (list *LinkedList) show() []int {
	if (*list).empty() {
		// 空链表
		return []int{}
	}
	var result []int
	p := (*list).head
	for p != nil {
		result = append(result, p.data)
		p = p.next
	}

	return result
}

仍然是平分检测：

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
59

func checkPalindrome2(list *LinkedList) bool {
	if (*list).empty() {
		// 为空
		return true
	}

	// p在后，q 在前
	p, q := list.head, list.head
	// 左半部分的数据
	lData := []int{p.data}
	// 右半部分的数据
	rData := []int{}
	for q.next != nil {
		if q.next.next != nil {
			// 后面第二节点不为空，可以走两步
			p = p.next
			q = q.next.next
      // 采集左半部分数据
			lData = append(lData, p.data)
		} else {
			// 中间有两个值，退出查找中间
			lData = append(lData, p.data)
			break
		}
	}
	// 从中间值开始继续往右，采集右半部分数据
	for p != nil {
		rData = append(rData, p.data)
		p = p.next
	}
	rData = reverse(rData)
	for i := 0; i < len(lData); i++ {
		if lData[i] != rData[i] {
			return false
		}
	}
	return true
}
// 翻转 slice
func reverse(s []int) []int {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
	return s
}

func main() {
	var list LinkedList
	list.init()

	list.appendMany(2)
	fmt.Printf("%v: %t \n", list.show(), checkPalindrome2(&list))

	list.appendMany(5, 8, 8, 5, 2)
	fmt.Printf("%v: %t \n", list.show(), checkPalindrome2(&list))

	list.appendMany(1)
	fmt.Printf("%v: %t \n", list.show(), checkPalindrome2(&list))
}

输出结果：

1
2
3

[2]: true
[2 5 8 8 5 2]: true
[2 5 8 8 5 2 1]: false

上面的方法使用了临时slice，空间复杂度为 \(O(n)\)。其实可以把右半部分的链表给翻转，遍历比较左右部分链表即可把空间复杂度降为 \(O(1)\)。

优化如下：

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

// 从 startNode 开始翻转，包含 startNode
func reverseLinkedList(startNode *Node) *Node {
	if startNode == nil || startNode.next == nil {
		return nil
	}
	var pre *Node
	cur := startNode
	for cur != nil {
		next := cur.next
		cur.next = pre
		pre = cur
		cur = next
	}
	return pre
}

func checkPalindrome(list *LinkedList) bool {
	if (*list).empty() {
		// 为空
		return true
	}

	// p在后，q 在前
	p, q := list.head, list.head
	for q.next != nil {
		if q.next.next != nil {
			// 后面第二节点不为空，可以走两步
			p = p.next
			q = q.next.next
		} else {
			// 中间有两个值
			break
		}
	}
	tmp := reverseLinkedList(p.next) // 翻转p的右边，即右半部分
	left := list.head
	right := tmp
	for right != nil {
		if left.data != right.data {
			p.next = reverseLinkedList(tmp) // 最后重置回原来的链表
			return false
		}
		left = left.next
		right = right.next
	}
	p.next = reverseLinkedList(tmp) // 最后重置回原来的链表
	return true
}

注意，上面有一个 p.next = reverseLinkedList(tmp)，是为了不破坏单链表原来的顺序，所以给予重置。

技术
算法 双指针 夹逼 链表 单链表 双链表 python go
本文由作者按照 CC BY 4.0 进行授权
文章内容