【leetcode】回文链表（Palindrome Linked List）【python】三种方法

青旅半醒 2022-05-13 05:16 147阅读 0赞

[题目链接][Link 1]  
![在这里插入图片描述][70]

--------------------

## 时间复杂度O(N),空间复杂度O(N) ##

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    
    def str_isPalindrome(nums, length):
        i, j = 0, length - 1
        while i != j:
            if nums[i] != nums[j]:
                return False
            if i == length / 2:
                return True
            i += 1
            j -= 1
        return True
    
    class Solution:
        def isPalindrome(self, head):
            """ :type head: ListNode :rtype: bool """
            #脑残办法，直接将链表里面的数据放入数组中
            string = ''
            j = head
            if j == None:
                return True
            index = 0
            nums = [0] * 100000
            while j != None:
                nums[index] = j.val
                index += 1
                j = j.next
            return str_isPalindrome(nums, index)

--------------------

## \#\# 时间复杂度O(N),空间复杂度O(N/2) \#\# ##

**1.这里使用了快慢指针，快慢指针典型的应用就是判断链表是否存在环，另外一个应用就是找出链表的中位数，这个地方就是使用快慢指针来寻找链表的中位数**  
**2.另外使用栈来存取前半段的数，使用list.insert()方法，使用数组来模拟栈**

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    
    class Solution:
        def isPalindrome(self, head):
            """ :type head: ListNode :rtype: bool """
            if head == None or head.next == None:
                return True
            slow = fast = head #定义快慢指针来确定链表的中点
            list = []
            while fast and fast.next:
                list.insert(0, slow.val) #使用队列来模拟栈
                slow = slow.next
                fast = fast.next.next
            if fast:
                slow = slow.next  #有奇数个节点，忽略
            for val in list:
                if val != slow.val:
                    return False
                slow = slow.next
            return True

--------------------

## \#\# 时间复杂度O(N),空间复杂度O(1) \#\# ##

**1. 采用快慢指针来找到链表中点**  
**2. 找到中点之后，采用空间复杂度O(1)的反转链表的算法，将链表反转，需要注意的是，反转过程中语句的顺序，head = head.next一定要在第二句，而不是最后，要不然就断链了，因为p指向了head更改p相当于更改了head,当head指向next之后，才能更改p**

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    
    class Solution:
        def ReverseList(self, head):
            new_head = None
            while head:
                p = head
                head = head.next
                p.next = new_head
                new_head = p
                #head = head.next
            return new_head
    
        def isPalindrome(self, head):
            """ :type head: ListNode :rtype: bool """
            slow = fast = head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            if fast:
                slow = slow.next
            new_head = self.ReverseList(slow)
            while new_head:
                if head.val != new_head.val:
                    return False
                head = head.next
                new_head = new_head.next
            return True

[Link 1]: https://leetcode-cn.com/problems/palindrome-linked-list/description/
[70]: /images/20220513/7285157f12a7448f951ef9484cb66d7b.png