回文链表

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. 快慢指针翻转后半段

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    fast := head
    slow := head
    for fast != nil && fast.Next != nil{
        fast = fast.Next.Next
        slow = slow.Next
    }
    head2 := reverseList(slow)
    for head != nil && head2 != nil {
        if head.Val != head2.Val {
            return false
        }
        head = head.Next
        head2 = head2.Next
    }
    return true
}

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

4. 参考

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