LeetCode 234 Palindrome Linked List 题解

发表于 | 阅读次数:

题目

　　Given a singly linked list, determine if it is a palindrome.

　　Follow up:

　　Could you do it in O(n) time and O(1) space?

题意分析

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

　　所谓回文，即从左往右和从右往左读都是一样的。例如：

　　“abcdefgfedcba”

　　1->2->3->3->2->1

　　我们现在要做的，就是判断给定的链表是否满足这个特性。

　　这题还有一个难点，就是时间复杂度与空间复杂度的限制。特别是空间复杂度限制太严格了。

思路与代码

递归

　　这题我第一反应是开辟一个数组，把链表倒着存进去，然后逐一和原链表的的值比对，看是否都一致。但这种思路需要的空间复杂度是o(n)。

　　因此，我就想怎么能节省空间复杂度呢？就想到用递归。其实递归有点作弊的意思，因为虽然局部变量的空间复杂度只有o(1)，但程序运行时的函数调用栈需要消耗的栈空间是o(n)，这与直接在局部变量定义一个栈来做是一样的，只是会逃过空间复杂度的检查。

　　下面是递归的思路：

  1. 求链表的中点。
  2. 递归的终止条件是到达链表的中点返回，如果没有到达中点则继续寻找下一个结点。
  3. 假设有链表：n1->n2->n3…->nk->nl…->nm->nn…->ny->nz。假如链表nl…nm是回文的，那么nk到nn回文当且仅当nk.val == nn.val。
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int length = 0;
    private int mid = 0;
    public boolean isPalindrome(ListNode head) {
        if(head == null){
            return true;
        }
        int length = 0;
        ListNode temp = head;
        while(temp != null){
            length++;
            temp = temp.next;
        }
        int mid = (length+1) / 2;
        this.length = length;
        this.mid = mid;
        ListNode result = isEqual(head,1);
        if(result != null){
            return true;
        }else{
            return false;
        }
    }
    
    private ListNode isEqual(ListNode node,int index){
        if(mid == index && length % 2 == 1){
             if(node.next != null){
                return node.next;
            }else{
                return node;
            }
        }else if(mid == index && length % 2 == 0){
                if(node.val == node.next.val){
                    if(node.next.next != null){
                        return node.next.next;
                    }else{
                        return node.next;
                    }
                }else{
                    return null;
                }
        }else{
            ListNode result = isEqual(node.next,(index+1));
            if(result == null){
                return null;
            }else if(node.val == result.val){
                if(result.next != null){
                    return result.next;
                }else{
                    return result;
                }
            }else{
                return null;
            }
        }
    }
}

　　这里找中点直接用了遍历这个链表的方法。在递归算法里，如果子链表是回文的，则返回子链表最后一个结点的引用。子链表返回的引用的下一个结点就是父链表的最后一个结点。此时判断父链表的第一个结点与最后一个结点的值是否相等就可以判断父链表是否是回文的了。

解法二

　　这个解法我觉得比递归的好很多，是网上比较权威的一个解法，这里记录一下。

　　单链表最令人郁闷的，就是只能引用下一个结点，不能引用上一个结点，遍历路径是单向的。但很多时候，我们希望遍历的顺序往往是反着的。像这题这个判断回文，如果能反着遍历链表，就很容易判断了。于是，很自然的，我们就想着能不能将链表逆转。后面的逆转链表算法，十分经典，非常值得借鉴。

　　解法步骤：

  1. 获得链表中点的结点。
  2. 将后半段链表逆转。
  3. 分别遍历前半段和后半段链表，逐个比较每个结点的值，如果全部相等，则是回文的；有一个不相等，则不是回文的。

　　其中寻找中点的算法，是判断链表是否有环算法的变形，用到了快慢指针，也非常经典。

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
39
40
41
42
43
44
45
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null){
            return true;
        }
        ListNode mid = findMiddle(head);
        mid.next = revert(mid.next);
        ListNode p1 = head;
        ListNode p2 = mid.next;
        while(p2 != null && p1.val == p2.val){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2 == null;
    }
    
    private ListNode findMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    private ListNode revert(ListNode head){
        ListNode prev = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}

　　找单链表中点算法，主要是设置了一个慢指针，一个快指针。慢指针每次循环前进一步，快指针则前进两步。不难看出，在整个循环过程中，快指针的位置始终是慢指针的两倍，那么当快指针将要跑出链表时，慢指针则刚好在中点位置。

　　逆转链表算法就非常简单了，只是单纯的遍历。维护前后两个链表，每次循环把后链表的一个结点给前链表，前链表是已经逆转的链表，后链表则还保持原来的顺序。当遍历到最后一个结点时，则整个链表都被逆转了。