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
// @Title: 回文链表 (Palindrome Linked List)
// @Author: 15816537946@163.com
// @Date: 2019-11-20 23:10:59
// @Runtime: 16 ms
// @Memory: 5.9 MB
/*
 * @lc app=leetcode.cn id=234 lang=golang
 *
 * [234] 回文链表
 *
 * https://leetcode-cn.com/problems/palindrome-linked-list/description/
 *
 * algorithms
 * Easy (38.46%)
 * Likes:    258
 * Dislikes: 0
 * Total Accepted:    35K
 * Total Submissions: 90.9K
 * Testcase Example:  '[1,2]'
 *
 * 请判断一个链表是否为回文链表。
 * 
 * 示例 1:
 * 
 * 输入: 1->2
 * 输出: false
 * 
 * 示例 2:
 * 
 * 输入: 1->2->2->1
 * 输出: true
 * 
 * 
 * 进阶:
 * 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
 * 
 */
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 // 复杂度分析: 时间O(n), 空间O(1)
//  使用快慢指针寻找链表中点,然后反转后半部分,再分别从开头和中点处遍历比较
/*
unc isPalindrome(head *ListNode) bool {
	if head == nil ||  head.Next == nil {
		return true
	}

	// 1. 快慢指针寻找链表中点
	slow,fast := head, head
	for fast != nil && fast.Next != nil {
		fast =fast.Next.Next
		slow = slow.Next
	}

	// 2. 从中点开始反转链表找后半部分
	var prev, cur *ListNode = nil, slow
	for cur != nil {
		next := cur.Next // 先记录下一个节点
		cur.Next = prev // 当前节点的引用, 指向上一个节点
		prev = cur  // 保存指针状态
		cur = next // 指针后移
	}

	// 3. 分别从开头和中点处遍历比较
	// mid := prev
	for prev != nil {
		if prev.Val != head.Val {
			return false
		}
		// 4. 指针后移
		prev= prev.Next
		head = head.Next
	}
	return true
}
*/

// 使用快慢指针寻找链表中点,再反转后半部分,再分别从起点和中点比较
func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}

	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	// 从中点开始反转链表找后半部分
	var prev, cur *ListNode = nil, slow
	for cur != nil {
		next := cur.Next // 先记录下一个节点
		cur.Next = prev // 当前节点的引用,指向上一个节点
		prev = cur      // 保存指针状态
		cur = next      // 指针后移
	}

	// 分别从开头和中点处遍历
	for prev != nil {
		if prev.Val != head.Val {
			return false
		}

		// 指针后移
		prev = prev.Next
		head = head.Next
	}
	return true

}