234. 回文链表

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

示例 1:

输入: 1->2 输出: false 示例 2:

输入: 1->2->2->1 输出: true 进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解:
思路一：
  • 利用快慢指针找到中间节点，并将中间节点之前的元素入栈
  • 然后遍历中间节点之后的元素
  • 如果与栈顶一致， 则栈pop(). 遍历下一个
  • 如果与栈顶不一致， 则 return false
  • 遍历完链表， 一直一样， 且最后 栈空。 return ture

代码如下;

 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

 // 使用栈
    public static boolean isPalindrome(ListNode head) {

        if (head == null || head.next == null) return true;
        Stack <Integer>s = new Stack();

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            s.push(slow.val);

            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast != null) slow = slow.next;

        while (slow != null){
            int val = s.pop();
            if (val != slow.val) return false;

            slow = slow.next;
        }

        return s.isEmpty();
    }

时间复杂度 : O(N) 遍历整遍链表，N为链表中元素的个数

空间复杂度 : O(N) 使用了额外的栈存储空间

思路二;
  • 使用数组
  • 遍历将链表中所有元素都加入数组
  • 定义两个指针 begain 和 end，分别指向链表的开头和结尾
  • 比较，begain 和 end 指向元素一样是， begain ++, end – 继续比较
  • 不一样时，return false
  • 遍历到最后，一直一样。 则为回文。 return true.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

   // 使用数组
    public static boolean isPalindrome1(ListNode head) {

        ArrayList list = new ArrayList();
        while (head != null){
            list.add(head.val);
            head = head.next;
        }

        System.out.println(list);
        int begain = 0;
        int end = list.size() - 1;

        while (begain <= end){
            if (!list.get(begain).equals(list.get(end))) return false;
            begain ++;
            end --;
        }

        return true;
    }

时间复杂度 : O(N) 遍历整遍链表，N为链表中元素的个数

空间复杂度 : O(N) 使用了额外的栈存储空间

思路三:
  • 先找到链表的中间节点middle
  • 反转middle
  • 从头到位比较 head 和 反转后的mid
  • 如果不一致， 则返回 false
  • 如果一致，继续向下遍历
  • 遍历到末尾，一致是一样， 则为回文

代码如下:

 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

public static boolean isPalindrome(ListNode head){

        ListNode middel = middle(head);
        ListNode revertHead = revert(middel);

        while (revertHead != null){
            if (revertHead.val != head.val) return false;

            head = head.next;
            revertHead = revertHead.next;
        }

        return true;
    }

    public static ListNode middle(ListNode head){

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){

            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast != null) slow = slow.next;
        return slow;
    }

    public static ListNode revert(ListNode node){

        ListNode newHead = null;
        while (node != null){
            ListNode tmp = node.next;
            node.next = newHead;
            newHead = node;
            node = tmp;
        }

        return newHead;
    }

时间复杂度 : O(N) 遍历整遍链表，N为链表中元素的个数

空间复杂度 : O(1) 没有使用额外的栈存储空间