回文链表

1. 题目描述

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

2. 思路

1. 思路一
   • 遍历链表存入数组中
   • 双指针判断数组是否回文
2. 思路二
   1. 遍历两次
   2. 翻转后半段链表
3. 思路三
   • 快慢指针
   • 快指针走两步，慢指针走一步，直到快指针走到尾部，此时慢指针走到链表的一半
   • 翻转后半部分链表
   • 从头开始遍历两个链表是否相等

3. 实现

3.1. 栈

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    stack := make([]int, 0)
    current := head
    for current != nil {
        stack = append(stack, current.Val)
        current = current.Next
    }

    left := 0
    right := len(stack)-1
    for left < right {
        if stack[left] != stack[right] {
            return false
        }
        left++
        right--
    }

    return true
}

3.2. 遍历两次翻转后半段

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    count := 0
    h := head
    for h != nil {
        count++
        h = h.Next
    }

    h = head
    for i := 0; i < count/2; i++ {
        h = h.Next
    }
    l2 := reverseList(h)
    l1 := head
    for l1 != nil && l2 != nil {
        if l1.Val != l2.Val {
            return false
        }
        l1 = l1.Next
        l2 = l2.Next
    }

    return true
}

func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    current := head
    var next *ListNode
    for current != nil {
        next = current.Next
        current.Next = pre
        pre = current
        current = next
    }
 
    return pre
}

3.3. 快慢指针翻转后半段

package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
	if head == nil {
		return false
	}

	//快慢指针找到后半段
	slow := head
	fast := head
	for fast != nil {
		if fast.Next != nil {
			fast = fast.Next.Next
		} else {
			fast = fast.Next
		}
		slow = slow.Next
	}

	//翻转后半段
	var prev *ListNode
	for slow != nil {
		next := slow.Next
		slow.Next = prev
		prev = slow
		slow = next
	}

	//比较后半段
	for prev != nil && head != nil {
		if prev.Val != head.Val {
			return false
		}
		prev = prev.Next
		head = head.Next
	}

	return true
}

4. 参考

• 234. 回文链表 - 力扣（LeetCode）