数据结构与算法---链表---回文链表

回文链表

234.回文链表

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

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

---

思路1

建立两个指针，left和right，分别指向链表的头和尾
判断left.vlaue和right.value是否相等，相等则left = left.next，right = ？
问题来了，right的前一个指针找不到了
因此，不满足要求

但是，可以将链表放于数组中，然后就可以利用left和right指针，遍历数组了

class Solution {
    public boolean isPalindrome(ListNode head) {
        //边界条件
        if(head == null) return false;
        if(head.next == null) return true;
		
		//获取链表长度，其实用可变数组更好
        int count = 0;
        ListNode tempNode = head;
        while(tempNode != null){
            count++;
            tempNode = tempNode.next;
        }
		
		//创建数组
        int[] array = new int[count];
        tempNode = head;
        int count2 = 0;
        //链表->数组赋值
        while(tempNode != null){
            array[count2] = tempNode.val;
            tempNode = tempNode.next;
            count2++;
        }

        int left = 0;
        int right = array.length - 1;
		
		//查找数组
        while(left <= right){
            if(array[left] == array[right]){
                left++;
                right--;
            }else{
                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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

思路2

新建一个链表B，存储的内容是链表A的翻转
然后比较A和B的值即可。

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null) return true;
        if(head.next == null) return true;

        //不改变原来的头结点
        ListNode pHead = head;
        ListNode reverseHead = reverseList(pHead);

        while(head != null){
            if(head.val == reverseHead.val){
                head = head.next;
                reverseHead = reverseHead.next;
            }else{
                return false;
            }
        }
        return true;
    }

    public ListNode reverseList(ListNode head)
    {
        if(head == null || head.next == null) return head;
        
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
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

该代码有点问题
[1, 1, 2, 1]的时候，返回的是true
其他[1,2] 或者 [1, 2, 3] 或者[1, 2, 1, 2, 7]都是返回正确值
目前还没看出问题

要是能打印下，看看链表节点就好了，但是，使用LeetCode没法打印看，那么，拿到Eclipse中调试下

经过调试，发现

翻转完之后，原来的链表被破坏
仔细考虑下，递归翻转链表的最后一步，就是将倒数第二个指针与第一个指针之间的相互转换。
也就是说，head本身指向的还是第一个结点，但是，head的next就是null了

为何[1, 2]是对的？
是因为：
原链表是1->2
翻转后是2->1
原链表被破坏为1->null
判断2 != 1，返回false

[1, 2, 1, 2, 7]
原链表是1->2->1->2->7
翻转后是7->2->1->2->1
原链表被破坏为1->null
判断1 != 3，返回false

[1, 1, 2, 1]
原链表是1->1->2->1
翻转后是1->2->1->1
原链表被破坏为1->null
判断1 == 1
下一步原链表为null
返回true

[1, 2, 2, 1]
原链表是1->2->2->1
翻转后是1->2->2->1
原链表被破坏为1->null
判断1 == 3
下一步原链表为null
返回ture
蒙对了

也就是：
如果需要判断的链表本身 是 翻转链表，这个程序判断的都是正确的

如果需要判断的链表本身不是翻转链表

• 如果第一个与最后一个元素相等，则返回true，
• 如果第一个元素与最后一个元素不相等，则返回false

package 链表;

public class 回文链表 {
	
	public static class ListNode {
		 int val;
		 ListNode next;
		 ListNode(int x) { val = x; }
		 public String toString() {
			return val + " -> " + next;
		}
	}
	
	public static void main(String[] args)
	{
		ListNode head = new ListNode(1);
		head.next = new ListNode(1);
		head.next.next = new ListNode(2);
		head.next.next.next = new ListNode(1);
		System.out.println("输入的链表：" + head);
		
		回文链表 hwlb = new 回文链表();
		System.out.println("是否为回文链表：" + hwlb.isPalindrome(head));
	}
	
	public boolean isPalindrome(ListNode head) {
        if(head == null) return true;
        if(head.next == null) return true;

        //不改变原来的头结点
        ListNode pHead = new ListNode(-1);
        System.out.println("翻转前的链表：" + pHead);
        ListNode reverseHead = reverseList(pHead);
        System.out.println("翻转后的链表：" + reverseHead);
        
        System.out.println("head：" + head);
        System.out.println("pHead：" + pHead);
        
        while(head != null){
            if(head.val == reverseHead.val){
                head = head.next;
                reverseHead = reverseHead.next;
            }else{
                return false;
            }
        }
        return true;
    }

    public ListNode reverseList(ListNode head)
    {
        if(head == null || head.next == null) return head;
        
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

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

终于搞明白了自己程序问题在哪，在于翻转的时候，把原链表结构改变了

那么，改正程序，简单点，再翻转一遍
还是不行，
还是自己跟自己玩

这么看来，只能是新建一个链表了

新建一个备份链表

	public ListNode copyList(ListNode head)
	{
		//新建一个备份链表
        ListNode dummyHead = new ListNode(-1);
        ListNode newHead = dummyHead;
        
        ListNode currentHead = head;
        while(currentHead != null)
        {
        	ListNode tempNode = new ListNode(currentHead.val);
        	newHead.next = tempNode;
        	newHead = tempNode;
        	currentHead = currentHead.next;
        }
        return dummyHead.next;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输入的链表：1 -> 1 -> 2 -> 1 -> null
备份翻转前的链表：1 -> 1 -> 2 -> 1 -> null
翻转后的链表：1 -> 2 -> 1 -> 1 -> null
翻转前的链表：1 -> 1 -> 2 -> 1 -> null
是否为回文链表：false

终于解决问题！

---

思路3

找出中间节点
如果链表个数为奇数，1->2->1，那么中间节点很容易找出为2
如果链表个数为偶数，1->2->3->4，那么我们规定中间节点为2

这是因为：
在链表个数为奇数的时候，找到中间节点不需要对比（本身链表就是奇数，中间节点只有一个），需要开始比较的节点是 中间节点的下一个元素
在链表个数为偶数的时候，如果也想开始比较的是 中间节点的下一个元素，也就是从3开始，那么中间节点设为2，就可以满足需求。

假设现在链表是：1->2->3->2->1，那么该链表的中间节点mid是3
翻转3后面的节点，变为
左边的链表：1->2->3
右边的链表：1->2->null
两个链表做对比

相等则比较下一对
不相等则返回false
如果右边链表的下一个为null，说明比较完成，那么返回true

那么，如何找到中间节点呢？
借助快慢指针

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null) return true;//空链表
        if(head.next == null) return true;//只有一个节点
        if(head.next.next == null) return head.val == head.next.val;//只有两个节点

        ListNode midNode = midList(head);
        ListNode rightHead = reverseList(midNode.next);
        //不改变原来的头结点
        ListNode leftHead = head;

        while(rightHead != null){//注意是右边节点判断
            if(leftHead.val == rightHead.val){
                leftHead = leftHead.next;
                rightHead = rightHead.next;
            }else{
                return false;
            }
        }
        return true;
    }

    //找出中间节点
    public ListNode midList(ListNode head)
    {
        //快指针
        ListNode fastNode = head;
        //慢指针
        ListNode slowNode = head;
        while(fastNode.next != null && fastNode.next.next != null){
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        return slowNode;
    }

    //翻转链表
    public ListNode reverseList(ListNode head)
    {
        if(head == null || head.next == null) return head;
        ListNode newHead = null;

        while(head != null) 
        {
            ListNode tempNode = head.next;
            
            head.next = newHead;
            newHead = head;
            head = tempNode;
        }
        return newHead;
    }
}
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

如果要求原链表不能改变怎么办？

由于右边链表进行了翻转，破坏了原来链表的结构
只需要在return前，再次对右边的链表进行翻转即可

ListNode rightOldHead = rightHead;
也就是在两个return前，加上reverseList(rightOldHead)即可

---

居然找到了MJ大神PPT上截图的原地址，哈哈