原创

234. 回文链表

234. 回文链表

链接

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

示例1

输入: 1->2
输出: false

``

示例2

```shell

输入: 1->2->2->1

输出: true

解题思路

type ListNode struct {
	Val  int
	Next *ListNode
}

// 思路:先使用快慢指针定位链表中点,然后反转中点的后半部分,最后分别从开头和中点处遍历比较是否是回文链表
func isPalindrome(head *ListNode) bool { // 使用快慢指针寻找链表中点,然后反转后半部分,再分别从开头和中点处遍历比较
	if head == nil {
		return true
	}
	// 1. 快慢指针寻找链表中点
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next // 快指针一次走两步
		slow = slow.Next      // 慢指针一次走一步
	}
	// 2. 从中点开始反转链表后半部分
	var pre, cur *ListNode = nil, slow
	for cur != nil {
		next := cur.Next // 先记录下下一个节点,不然一会就没了
		cur.Next = pre   // 当前节点指向上一个节点
		pre = cur        // 指针后移
		cur = next
	}
	// 3. 分别从开头和中点处遍历比较
	mid := pre
	for mid != nil {
		if head.Val != mid.Val { // 比较每一个元素
			return false
		}
		mid = mid.Next // 指针后移
		head = head.Next
	}
	return true
}


// 解题2,取出链表中的数

func isPalindrome2(head *ListNode) bool {
	// 获取 list 中的值
	nums := make([]int, 0, 64)
	for head != nil {
		nums = append(nums, head.Val)
		head = head.Next
	}

	// 按照规则对比值
	l, r := 0, len(nums)-1
	for l < r {
		if nums[l] != nums[r] {
			return false
		}
		l++
		r--
	}
	return true
}

// 题解3
func isPalindrome3(head *ListNode) bool {
  if head == nil {
    return true
  }
  var res []*ListNode
  for head != nil {
    res = append(res, head)
    head = head.Next
  }
  left := 0
  right := len(res) - 1
  for left < right {
    if res[left].Val != res[right].Val {
      return false
    }
    left++
    right--
  }
  return true
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 234 回文链表

    我们仍然是要使空间复杂度为O(1) 的,所以还是要回到纯链表的操作。结合之前的练习可以采用原地链表反转的算法之后再和原链表挨个比较,整个反转再比较的话是行不通的...

    木瓜煲鸡脚
  • LeetCode 234. 回文链表

    freesan44
  • Leetcode 234. 回文链表

    若要满足 O(1) 空间复杂度,则不能借助于列表或栈结构存储数据。因为单链表不像字符串可以进行直接访问,所以这里采用的方式为,找到单链表中间元素,并反转单链表前...

    zhipingChen
  • LeetCode 234:回文链表 Palindrome Linked List

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

    爱写bug
  • LeetCode 234:回文链表 Palindrome Linked List

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

    爱写bug
  • LeetCode 234. 回文链表(快慢指针+链表反转)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/palindrome-linked-list 著作权...

    Michael阿明
  • 链表问题-LeetCode 206、234、160(反转,回文,公共结点)

    示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

    算法工程师之路
  • 回文链表

    一份执着✘
  • 回文链表

    大忽悠爱学习

扫码关注云+社区

领取腾讯云代金券