Sword finger offer 09   Queue with two stacks

Implement a queue with two stacks. The declaration of the queue is as follows. Please implement its two functions appendTail and deleteHead to insert integers at the end of the queue and delete integers at the head of the queue respectively. (if there are no elements in the queue, delete head   Operation return (- 1)

Example 1:

Input:
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
Output: [null,null,3,-1]

Example 2:

Input:
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
Output: [null,-1,null,null,5,2]

Method 1: double stack

Two stacks are maintained. The first stack supports insertion and the second stack supports deletion.

java:

class CQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    
    public CQueue() {
        stack1 = new LinkedList<Integer>();
        stack2 = new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        // If the second stack is empty
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        } 
        if (stack2.isEmpty()) {
            return -1;
        } else {
            int deleteItem = stack2.pop();
            return deleteItem;
        }
    }
}

C++:

​
class CQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    
    public CQueue() {
        stack1 = new LinkedList<Integer>();
        stack2 = new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        // If the second stack is empty
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        } 
        if (stack2.isEmpty()) {
            return -1;
        } else {
            int deleteItem = stack2.pop();
            return deleteItem;
        }
    }
}

Palindrome linked list

Give you the head node of a single linked list. Please judge whether the linked list is a palindrome linked list. If yes, return true; Otherwise, false is returned.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Idea:

1. Reverse the second half of the linked list

Find the central node through the speed pointer, and then reverse the linked list.

  The specific codes are as follows:

public boolean isPalindrome(ListNode head) {
    ListNode fast = head, slow = head;
    //Find the midpoint through the fast and slow pointer
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    //If fast is not empty, the length of the linked list is odd
    if (fast != null) {
        slow = slow.next;
    }
    //Reverse the second half of the linked list
    slow = reverse(slow);

    fast = head;
    while (slow != null) {
        //Then compare and judge whether the node values are equal
        if (fast.val != slow.val)
            return false;
        fast = fast.next;
        slow = slow.next;
    }
    return true;
}

//Reverse linked list
public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

2. Use stack to solve the problem

We know that the stack is a data structure of first in and last out. Here, you can also use the stack to store all the nodes of the linked list in the stack first, and then out of the stack one by one. This is equivalent to the access of the linked list from back to front. It can also be solved in this way

public boolean isPalindrome(ListNode head) {
    ListNode temp = head;
    Stack<Integer> stack = new Stack();
    //Store the value of the linked list node in the stack
    while (temp != null) {
        stack.push(temp.val);
        temp = temp.next;
    }

    //Then out of the stack
    while (head != null) {
        if (head.val != stack.pop()) {
            return false;
        }
        head = head.next;
    }
    return true;
}

Circular linked list

Give you a head node of the linked list to judge whether there are links in the linked list.

If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list. In order to represent the rings in a given linked list, the evaluation system uses the integer pos to represent the position where the tail of the linked list is connected to the linked list (the index starts from 0). If pos is - 1, there is no ring in the linked list. Note: pos is not passed as a parameter, but only to identify the actual situation of the linked list.

Returns true if there are links in the linked list. Otherwise, false is returned.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: there is a ring in the linked list, and its tail is connected to the second node.

Example   2:

Input: head = [1,2], pos = 0
Output: true
Explanation: there is a ring in the linked list, and its tail is connected to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: there are no links in the linked list.

Idea:

Method 1: hash table

public boolean hasCycle(ListNode head) {
    Set<ListNode> set = new HashSet<>();
    while (head != null) {
        //If repeated, there is a ring
        if (set.contains(head))
            return true;
        //Otherwise, the current node is added to the collection
        set.add(head);
        head = head.next;
    }
    return false;
}

Method 2: speed pointer

public class solution{
    public boolean hasCycle(ListNode head){
        if(head == null || head.next == null){
            return false;        
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast){
            if(fast == null || fast.next == null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}