LeetCode链表反转(206-234)

发表于 | 分类于 | 阅读次数

这篇文章主要介绍了两个重要思想：1、怎样以一次就找到链表的中间节点。2、在空间复杂度为O(1)的情况下反转链表

进阶条件下，判断回文链表

题目链接，主要讲解进阶要求下的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return True
        
        p_fast = head
        p_slow = head
        
        while True:
            if not p_fast.next:
                break
            elif not p_fast.next.next:
                p_slow = p_slow.next
                break
            p_fast = p_fast.next.next
            p_slow = p_slow.next
        
        # get mid point
        p_slow = self.reverseList(p_slow)
        while p_slow:
            if head.val!=p_slow.val:
                return False
            head = head.next
            p_slow = p_slow.next
        return True
        
    def reverseList(self,head):
        new_head=None
        while head:
            _secend = head
            head = head.next
            _secend.next = new_head
            new_head = _secend
        return new_head

之前做过判断过数字是否为回文数，思路主要是找到中点，然后判断前半部分和后半部分的反转是否相等，或者正序遍历前半部分，逆序遍历后半部分，依次比对。现在在链表不能直接得到长度，所以采用快慢指针的思路找中点。

1
2
3
4
5
6
7
8
9
10
p_fast = head
p_slow = head
while True:
    if not p_fast.next:
        break
    elif not p_fast.next.next:
        p_slow = p_slow.next
        break
    p_fast = p_fast.next.next
    p_slow = p_slow.next

其中慢指针总是指向头部和快指针的中点，当遍历束时，慢指针刚好指向整个链表的中点，ok，那这里会有朋友问了，一般涉及中点，就要考虑两种情况，长度为偶数或奇数，当然我们这里考虑了，两个if判断就是将奇偶两种长度的链表区分开来，如果是偶数长度，则慢指针再往后移动一步，因为此时直接跳出的话，慢指针是停在中点左面的。如果是奇数长度，则直接跳出，此时慢指针已经指在中点了。

1
2
3
4
5
6
7
8
def reverseList(self,head):
    new_head=None
    while head:
        _secend = head
        head = head.next
        _secend.next = new_head
        new_head = _secend
    return new_head

链表反转题目链接

这里我们先介绍一下这个空间复杂度为O(1)的链表反转函数，我主要说一下思路，我刚开始时没想到，是百度之后才明白的。弹出新的头部指向上一次产生的头部，比如：链表为1->2->3，当前弹出1称为新的头部指向上一次的头部(此时储存上一次的头部的节点刚初始化为None)，下一次，弹出2为新的头部指向上一次的头部1，此时的链表为两个(原本的链表被断开了)：2->1->None和3。

1
2
3
4
5
6
7
8
# get mid point
p_slow = self.reverseList(p_slow)
while p_slow:
    if head.val!=p_slow.val:
        return False
    head = head.next
    p_slow = p_slow.next
return True

接着我们继续讨论回文判断，此时我们得到了中间节点，直接进行反转，然后以得到的反转链表为基准，进行遍历，只要对应位置的值都相等就返回True。