Head changing problem of single linked list

If the algorithm related to the single linked list involves the head changing operation, the method needs to return the value

Simple question 1

Print the common part of two ordered linked lists

Question two

Judge whether a linked list is palindrome structure
[title] given the head node of a single linked list, please judge whether the linked list is palindrome structure.
[example] 1 - > 2 - > 1, return true; 1 - > 2 - > 2 - > 1, return true; 15 - > 6 - > 15, return true; 1 - > 2 - > 3, return false.
[example] if the length of the linked list is N, the time complexity reaches 0(N) and the additional space complexity reaches 0 (1).

Resolution:
What is the question structure of a linked list?
The positive and negative of the linked list are the same

Method 1: use the stack (the implementation is relatively simple, but it is only recommended to use it in the written examination, not in the interview)

Algorithm idea: it is realized with the help of stack, that is, the elements of linked list are put on the stack in turn. After all the elements are put into the stack, due to the first in and last out nature of the stack, the element at the top of the stack is the last value in the original linked list, and then comes out of the stack in turn in synchronization with the movement of the linked list pointer. Compare each element. If they are the same, they must be palindromes. This has obvious time and space complexity: O(N). The specific codes are as follows:

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();
        // Using head interpolation method to establish single chain table
        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("Palindrome structure");
        }else{
            System.out.println("Not palindrome structure");
        }
    }


    //Establishing single linked list by tail interpolation
    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;

    }


    // The stack space is used to judge the palindrome structure of the linked list. The time and space complexity are O (n)
    public boolean isPalindrome(ListNode node, int n)
    {
        ListNode listNode = node;
        if (listNode == null || listNode.next.next == null)
            return false;
        // Create a temporary stack space
        ListNode[] temp_stack = new ListNode[n];
        int i = -1;
        // Stack all nodes
        while (listNode != null)
        {
            temp_stack[++i] = listNode;
            listNode = listNode.next;

        }

        // Traverse the single linked list and compare it with the corresponding stack top node one by one; But be careful to add a node The condition that the next node is not empty, if node If next is empty, the traversal will be stopped
        while (node.equals(temp_stack[i--]) && node.next != null)
            node = node.next;


        // After traversal, if the next node of the single linked list is empty
        if (node.next == null)
            return true;

        return false;
    }

    //Print single linked list
    public void display(){
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.data+" ");
            cur=cur.next;
        }
        System.out.println();
    }
}

At the same time, fast and slow pointers and stacks are used to reduce space complexity

At this time, the space complexity is O(n / 2) and the time complexity is O(n)

    // The method of fast and slow pointer is used to judge the palindrome structure, so that the spatial complexity can be O (1)
    public boolean isPalindrome2(ListNode node, int n) {
        if (node == null || node.next.next == null)
            return false;
        ListNode fast = node;
        ListNode slow = node;

        // In this way, for a single linked list, when the number of nodes is odd, slow will go to the middle position; When the number of nodes is even, the slow node is at the end of the first half of the linked list.
        // This kind of writing is very clever
        while (fast.next.next != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Create a temporary stack space
        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;
        // The nodes stored in the stack fight with the traversal of the linked list, and then compare them one by one
        while (start.data == temp_stack[j--].data)
        {
            // A condition for the end of traversal,
            if (start.next == mid || start.next.next == mid) return true;
            start = start.next;
        }

        return false;
    }

Using the fast and slow pointer (only the method of fast and slow pointer is provided, and other data structures can refer to the above)

The time complexity of this algorithm is O (n) and the space complexity is O (1). Among the three methods, this method is the best

Steps:
(1) Use the fast and slow pointers, which are fast and slow respectively. For each traversal, the fast pointer takes two steps and the slow pointer takes one step. When the fast pointer reaches the end of the chain, the slow pointer is in the middle (if the length of the chain list is odd, it is in the middle, and the subscript is n/2; if it is even, it is n/2 - 1);
(2) Reverse the nodes of the right half of the linked list to generate a new linked list, but the tail of the left linked list and the right linked list are slow nodes to obtain the tail nodes of the right linked list
(3) Traverse the left linked list and the right linked list at the same time, and compare the data fields of the two. If there is any inequality, execute return false. If all are equal, return true; However, the number of single and double nodes should be considered when traversing.
(4) Consider restoring the linked list before returning

 // The method of fast and slow pointer is used to judge the palindrome structure, so that the spatial complexity can be 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;

        // In this way, for a single linked list, when the number of nodes is odd, slow will go to the middle position; When the number of nodes is even, the slow node is at the end of the first half of the linked list.
        while (fast.next != null && fast != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }


        /* // There is a problem with this code. Even if the following while loop is executed, p.next = null is still displayed after printing;
        ListNode finalNode = new ListNode(111);

        // Reverse the linked list node from slow,
        ListNode p = slow;
        p.next = null;
        while (slow.next != null)
        {
            System.out.println(" ----------------------- ");
            System.out.println(slow.data);
            ListNode q = slow.next;
            q.next = p.next;
            p.next = q;
            slow = slow.next;
        }
        */
        ListNode p = slow.next;
        ListNode record_mid = slow;
        // After the following traversal, the next field of the p node is empty and slow is at the last node
        while (p != null)
        {
            ListNode pnext = p.next;

            // Reverse using linked list
            p.next = slow;
            // Reverse the next node
            slow = p;
            p = pnext;
        }


        ListNode q = slow; // save last node
        q.next = null;// This line of code cannot be less, because the next field of the last node in the original linked list is empty, but in the process of reversing the linked list, the next field of slow points to the penultimate node
        ListNode start = node;

        // slow traverses to the left and node traverses to the right until they meet. If the corresponding node values of the two are different, false is returned
        while (slow != start)
        {
            if (slow.data != start.data)
                return false;

            // When the number of nodes is even, the meeting of slow and node nodes is different
            if (slow.next == start)
                return true;
            start = start.next; // start move
            slow = slow.next; // slow move
        }

        // It is convenient to reverse the right half of the linked list later


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

        // Before returning, don't forget to reverse the right half of the linked list
        while (prev_q != record_mid)
        {
            ListNode qnext = prev_q.next;

            // Node reversal
            prev_q.next = q;
            q = prev_q;
            prev_q = qnext;
        }

        return true;
    }