初级算法-链表-回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

回文链表示例.jpg

摘一个示例做个说明.
示例 1：
输入：head = [1,2,2,1]
输出：true

条件分析:

1. 链表操作 -> 从前往后操作
2. 回文链表 -> 链表反转 、 字符串反转、数组反转

解决思路1:

1. 根据分析1,说明需要进行从前往后操作
2. 根据分析2,可以借助别的反转方式进行判断

先判断链表是否为空或者单节点.是则直接返回.定义可变链表和可变数组,然后采用迭代进行取值,添加节点值到数组中.转化为数组回文、字符串回文即可.

func isPalindrome(_ head:ListNode?) -> Bool{
    if head == nil || head?.next == nil  {
        return true
    }
    var tmp: ListNode? = head
    var list: Array<Int> = []
    while tmp != nil {
        list.append((tmp?.val)!)
        tmp = tmp?.next
    }
    
    for i in 0..<list.count/2 {
        if list[i] != list[list.count - 1 - i] {
            return false
        }
    }
    return true
}

测试用例:

// 回文链表
let fourNode = ListNode.init(1)
let threeNode = ListNode.init(2)
threeNode.next = fourNode
let secondNode = ListNode.init(3)
secondNode.next = threeNode
let firstNode = ListNode.init(2)
firstNode.next = secondNode
let headNode = ListNode.init(1)
headNode.next = firstNode

// 非回文链表
let fourNode1 = ListNode.init(9)
let threeNode1 = ListNode.init(6)
threeNode1.next = fourNode1
let secondNode1 = ListNode.init(5)
secondNode1.next = threeNode1
let firstNode1 = ListNode.init(2)
firstNode1.next = secondNode1
let headNode1 = ListNode.init(0)
headNode1.next = firstNode1

// 单链表
let node = ListNode.init(5)

考察要点:

• 栈
• 递归
• 链表
• 双指针