算法练习：判断一个链表是否为回文结构

算法练习：判断一个链表是否为回文结构

【题目】给定一个单链表的头节点head，请判断该链表是否为回文结构。
【例子】1->2->1， 返回true; 1->2- ->2->1，返回true; 15->6->15， 返回true;
1->2->3， 返回false。
【提高】如果链表长度为N，时间复杂度达到O(N)，能否做到额外空间复杂度达到O(1)？

解答本题用到了快慢指针的技巧，所以先介绍一下快慢指针，它主要作用是找到链表的中间节点。

链表快慢指针介绍：

慢指针slow一次走1步，快指针F一次走2步，fast刚越界时S刚好走到中间位置，边界条件需具体情况来定制。

边界条件包括快慢指针的起始位置，和循环（遍历）的终止条件，由此来控制慢指针slow的最终落点。

通常边界条件的设置有如下几种情况：

    //为避免段错误，假设前面已有空指针的判断
//边界条件一：
ListNode slow = head; 
ListNode fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;  
} //循环结束后，slow跑到mid处(奇数个node)或右半边第一个node处(偶数个node)，fast跑到尾节点或null处
 

//边界条件二：
ListNode slow = head; 
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;  
} //循环结束后，slow跑到mid处(奇数个node)或左半边最后一个node处(偶数个node)，fast跑到尾节点或null处


//边界条件三：
ListNode slow = head.next; 
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;   		
}  //循环结束后，slow跑到右半边第一个节点处（无论奇偶），fast跑到尾节点或倒数第二个节点处


//边界条件四：
ListNode slow = head; 
ListNode fast = head.next.next;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;  
} //循环结束后，slow跑到mid前一个位置(偶数个node)，或左半边倒数第二个node处(偶数个node)，fast跑到尾节点或倒数第二个节点处

其中方法二、方法三都用到了快慢指针的技巧

方法一： 利用栈

 public static boolean isPalindrome1(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        Stack stk = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stk.push(cur.val);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            if ( cur.val != stk.pop()) {
                return false;
            }
            cur = cur.next;
        }
        return true;
  }

方法二：栈 + 快慢指针 （在方法一的基础上，空间利用减少一半）

    public static boolean isPalindrome2(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        //快慢指针 slow  fast
        ListNode slow = head.next;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;   
            slow = slow.next;		
        }

        Stack stk = new Stack<>();
        while (slow != null) {
            stk.push(slow.val);
            slow = slow.next;
        }

        ListNode cur = head;
        while(!stk.isEmpty()) {
            if (cur.val != stk.pop()) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }

方法三：快慢指针 + 反转链表   ， 空间复杂度降为O(1)

//方法三： 反转链表的后半部分        时间复杂度O(N),空间复杂度O(1)
    public static boolean isPalindrome3(ListNode head) {
        //find mid node or left mid node by Mr.slow,  find tail-node by Mr.fast
        ListNode n1 = head;  //慢指针
        ListNode n2 = head;  //快指针
        while (n2.next != null && n2.next.next != null) {
            n1 = n1.next;   //n1跑到mid处(奇数个node)或左半边最后一个node处(偶数个node)
            n2 = n2.next.next;
        }
        //反转后半部分的链表的指针指向
        n2 = n1.next;
        n1.next = null;
        ListNode n3 = null;
        while (n2 != null) {
            n3 = n2.next;      //记录n2的下一个节点
            n2.next = n1;      //反转n2的next指向
            n1 = n2;           //n1移动到下一个
            n2 = n3;           //n2移动到下一个
        }
        n2 = head;  //n2 -> head
        n3 = n1;    //记录尾节点
        //判断链表是否为回文
        boolean res = true;
        while (n1 != null && n2 != null) {
            if (n1.val != n2.val) {
                res = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }
        //将原链表后半部分调整回去
        n2 = n3.next;
        n3.next = null;
        while (n2 != null) {
            n1 = n2.next;       //记录n2的下一个节点
            n2.next = n3;       //反转n2的next指向
            n3 = n2;            //n3移动到下一个
            n2 = n1;            //n2移动到下一个
        }
        return res;
    }

测试：

  public static void main(String[] args) {

        ListNode L1 = new ListNode(1);
        PushBack(L1,2);
        PushBack(L1,3);
        PushBack(L1,4);
        printList(L1);
        System.out.println(isPalindrome3(L1));

        PushBack(L1,4);
        PushBack(L1,3);
        PushBack(L1,2);
        PushBack(L1,1);
        printList(L1);
        System.out.println(isPalindrome3(L1));
    }

    public static void PushBack(ListNode head, int val) {
        ListNode cur = head;
        ListNode newNode = new ListNode(val);
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;
    }
    
    public static void printList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            System.out.print(cur.val + " -> ");
            cur = cur.next;
        }
        System.out.println(cur.val);
    }

//Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode() {
        val = 0;
        next = null;
    }

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
    
}

结果如下：

1 -> 2 -> 3 -> 4
false
1 -> 2 -> 3 -> 4 -> 4 -> 3 -> 2 -> 1
true