链表的回文结构(算法笔记)

链表的回文结构(算法笔记) 单链表的换头问题

如果涉及到单链表的相关算法题中涉及到换头 *** 作，方法需要返回值

简单问题一

打印两个有序链表的公共部分

问题二

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

解析：
什么是链表的会问结构？
链表正着和反过来是一样的

方法一：使用栈（实现较为简单，但是只推荐在笔试中使用，面试中不推荐）

算法思想：借助栈进行实现，即将链表的元素依次进栈。全部进栈之后，由于栈先进后出的性质，栈顶的元素即为原链表中的最后一个值，然后和链表指针的移动同步依次出栈，比较每个元素，如果都相同，则肯定是回文的。这样做明显时间和空间复杂度:O(N)。具体代码如下：

package ListNode;
import Pojo.ListNode;
class MyList{
    public static ListNode head;
    public MyList(){
        this.head=null;
    }
    public static void main(String[] args) {
        int arr[] = {10, 5, 6, 8, 1, 8, 6, 5, 10};

        MyList my = new MyList();
        // 采用头插法建立单链表
        for (int i =0; i < arr.length; i++)
            my.addLast(arr[i]);
        my.display();
        boolean a=my.isPalindrome(head, arr.length);
        if(a==true){
            System.out.println("是回文结构");
        }else{
            System.out.println("不是回文结构");
        }
    }


    //尾插法建立单链表
    public void addLast(int data){
        ListNode node=new ListNode(data);
        if(this.head==null){
            this.head=node;
        }else {
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next=node;
        }
        //return head;

    }


    // 使用栈空间进行链表的回文结构判断,时间和空间复杂度均为O（n）
    public boolean isPalindrome(ListNode node, int n)
    {
        ListNode listNode = node;
        if (listNode == null || listNode.next.next == null)
            return false;
        // 创建一个临时栈空间
        ListNode[] temp_stack = new ListNode[n];
        int i = -1;
        // 所有结点入栈
        while (listNode != null)
        {
            temp_stack[++i] = listNode;
            listNode = listNode.next;

        }

        // 遍历单链表，与对应的栈顶结点一一比较;但是要注意加上一个node.next结点不为空的条件，如果node.next为空，则停止遍历
        while (node.equals(temp_stack[i--]) && node.next != null)
            node = node.next;


        // 遍历完成后，如果单链表的下一个节点为空
        if (node.next == null)
            return true;

        return false;
    }

    //打印单链表
    public void display(){
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.data+" ");
            cur=cur.next;
        }
        System.out.println();
    }
}

同时利用快慢指针和栈以减少空间复杂度

此时空间复杂度为O(n / 2),时间复杂度为O(n)

    // 使用快慢指针的方法实现回文结构的判断，这样能够做到空间复杂度为O（1）
    public boolean isPalindrome2(ListNode node, int n) {
        if (node == null || node.next.next == null)
            return false;
        ListNode fast = node;
        ListNode slow = node;

        // 这样对于单链表，当结点个数为奇数时，slow会走到中间位置；当结点个数为偶数时，slow结点处于链表的前一半的末尾位置。
        // 这种写法很巧妙
        while (fast.next.next != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 创建一个临时栈空间
        ListNode[] temp_stack = new ListNode[n / 2];
        int j = -1;
        ListNode mid = slow.next;
        while (slow.next != null)
        {
            temp_stack[++j] = slow.next;
            System.out.println( temp_stack[j].data);
            slow = slow.next;
        }
        ListNode start = node;
        // 栈中存储的结点随着链表的遍历而出战，随后一一对比
        while (start.data == temp_stack[j--].data)
        {
            // 遍历结束的一个条件，
            if (start.next == mid || start.next.next == mid) return true;
            start = start.next;
        }

        return false;
    }

利用快慢指针实现（只提供方法快慢指针的方法，其他的数据结构参考上文即可）

此算法的时间复杂度为O（n），空间复杂度为O（1），三种方法中，此种方法最优

步骤：
（1）利用快慢指针，分别为fast和slow每一次遍历，快指针走两步，慢指针走一步，快指针走到链尾时，慢指针出于中间的位置（如果链表长度为奇数，则处于正中间，下标为n/2，如果为偶数，下标为n/2 - 1；
（2）将右半部分链表的结点进行逆置 *** 作，生成一个新的链表，但是左链表和右链表中的链尾都为slow结点，获取右链表的尾部结点
（3）同时遍历左链表和右链表，并且比较两者的的data域，如果有一处不相等，则执行return false。如果全部相等，则return true；但遍历的时候要考虑单双结点数的情况。
（4）可以考虑在返回之前，将链表还原

 // 使用快慢指针的方法实现回文结构的判断，这样能够做到空间复杂度为O（1）
    public boolean isPalindrome_usePointer(ListNode node, int n)
    {
        if (node == null || node.next.next == null)
            return false;
        ListNode fast = node;
        ListNode slow = node;

        // 这样对于单链表，当结点个数为奇数时，slow会走到中间位置；当结点个数为偶数时，slow结点处于链表的前一半的末尾位置。
        while (fast.next != null && fast != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }


        
        ListNode p = slow.next;
        ListNode record_mid = slow;
        // 经历完以下的遍历，p结点的next域为空，slow处于最后一个结点位置
        while (p != null)
        {
            ListNode pnext = p.next;

            // 使用链表进行反转
            p.next = slow;
            // 对下一个结点进行反转 *** 作
            slow = p;
            p = pnext;
        }


        ListNode q = slow; // save last node
        q.next = null;// 这一行代码不能少，因为原来的链表中最后一个结点的next域为空，但是在链表反转的过程中，slow的next域指向了倒数第二个结点
        ListNode start = node;

        // slow往左遍历，node往右遍历，直到相遇，若其中存在两者对应的结点值不同的情况，返回false
        while (slow != start)
        {
            if (slow.data != start.data)
                return false;

            // 结点数为偶数时，slow和node结点相遇的情况不同的情况
            if (slow.next == start)
                return true;
            start = start.next; // start move
            slow = slow.next; // slow move
        }

        // 方便后面再将该链表的右半部分逆序回来


        ListNode prev_q = q.next; // save the previous node of the last node

        // 返回之前，不要忘记把这个链表的右半部分逆序回来
        while (prev_q != record_mid)
        {
            ListNode qnext = prev_q.next;

            // 实现结点逆转
            prev_q.next = q;
            q = prev_q;
            prev_q = qnext;
        }

        return true;
    }