6. print linked list from end to end
Meaning: Interview question 06 Print linked list from end to end
Idea: first, traverse the linked list to get the length of the linked list, and use this length to initialize the array. Then traverse the linked list from the beginning to the end, and insert the traversed numbers into the array from the back to the front.
class Solution {
public int[] reversePrint(ListNode head) {
int len = 0;
ListNode p = head;
while (p != null) {
p = p.next;
len ++;
}
int[] res = new int[len];
p = head;
while (p != null) {
res[--len] = p.val;
p = p.next;
}
return res;
}
}
9. implement queue with two stacks
Meaning: Interview question 09 Implementing queues with two stacks
Idea: "out of queue" operation: pour all the data of one stack into another empty stack, and then the operation sequence of the other stack is the out of stack sequence of the queue.
class CQueue {
Stack<Integer> in;
Stack<Integer> out;
public CQueue() {
in = new Stack<>();
out = new Stack<>();
}
public void appendTail(int value) {
in.push(value);
}
public int deleteHead() {
if (out.isEmpty()) {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
return out.isEmpty() ? -1 : out.pop();
}
}
18. delete the node of the linked list
Meaning: Interview question 18 Delete the node of the linked list
Idea 1: to delete a node in the single linked list, first find the previous node pre of the node, and then point the next pointer of the pre to the next node of the node.
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head == null) {
return head;
}
if (head.val == val) {
return head.next;
}
ListNode p = head;
while (p.next != null) {
if (p.next.val == val) {
p.next = p.next.next;
break;
}
p = p.next;
}
return head;
}
}
Train of thought 2: the above train of thought 1 is an operation when the value of the linked list node cannot be modified. If the value of the linked list can be modified, or the title does not give the chain header node, only the node to be deleted is given.
At this time, we can use the following node values to overwrite the previous node values to complete the operation of deleting nodes. consult Interview question 02.03 Delete intermediate node
class Solution {
public void deleteNode(ListNode node) {
ListNode p = node;
ListNode q = node.next;
while (q.next != null) {
p.val = q.val;
p = p.next;
q = q.next;
}
p.val = q.val;
p.next = null;
}
}
22. the penultimate node in the lin k ed list
Meaning: Interview question 22 The penultimate node in the lin k ed list
Idea: fast and slow double pointer method. Let the fast pointer go k steps first, and then the fast pointer and the slow pointer go together. When the fast pointer reaches the end of the linked list, the slow pointer points to the penultimate node
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode p = head;
while (p != null && k > 0) {
p = p.next;
k --;
}
if (p == null && k > 0) {
return null;
}
ListNode q = head;
while (p != null) {
p = p.next;
q = q.next;
}
return q;
}
}
24. reverse linked list
Meaning: Interview question 24 Reverse linked list
Idea: recursion. First, reverse the following node of the current node, reverseList(head.next). This function returns the inverted chain header, that is, the last node. After this operation, the next node of the current node points to the tail node of the inverted linked list, that is, the head Next, head The next node of next points to the current node to complete the inversion.
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
ListNode next = reverseList(head.next);
head.next.next = head;
head.next = null;
return next;
}
}
25. merge two sorted linked lists
Meaning: Interview question 25 Merge two sorted linked lists
Idea: Double finger needling. Use two pointers to point to the header nodes of L1 and L2 respectively, if l1 Val < l2 Val, then add the node pointed to by L1 to the new linked list, otherwise add the node pointed to by L2 to the new linked list.
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(-1);
ListNode r = head;
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
r.next = l2;
l2 = l2.next;
} else {
r.next = l1;
l1 = l1.next;
}
r = r.next;
}
r.next = (l1 == null) ? l2 : l1;
return head.next;
}
}
30. stack containing min function
Meaning: Interview question 30 Stack containing min function
Idea: two stacks are used. One stack, data, is used to store data, and the other stack, min, is used to store the information of the minimum value in data.
1) When entering the stack, if the current element x is smaller than the top element in the min stack, the current element x is pushed into the data stack and the min stack at the same time.
2) When exiting the stack, if the exit element X is equal to the top element of min, then x will also pop up from the Min stack.
class MinStack {
Stack<Integer> data;
Stack<Integer> min;
/** initialize your data structure here. */
public MinStack() {
data = new Stack<>();
min = new Stack<>();
}
public void push(int x) {
data.push(x);
if (min.isEmpty() || x <= min.peek()) {
min.push(x);
}
}
public void pop() {
if (data.isEmpty()) {
return;
}
int num = data.pop();
if (num == min.peek()) {
min.pop();
}
}
public int top() {
if (data.isEmpty()) {
return -1;
}
return data.peek();
}
public int min() {
if (min.isEmpty()) {
return -1;
}
return min.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.min();
*/
31. stack push in and pop-up sequence
Meaning: Interview question 31 Stack push and pop sequence
Idea: build a stack to simulate the pressing and popping operations in the topic. Because the first number in the pop-up sequence must pop up at the top of the stack, such as
pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
When the first element 4 in the pop-up sequence is pushed out of the stack, 4 and the previous elements must be pushed into the stack in the stack pressing sequence. At this time, simulate the pop-up of element 4 at the top of the stack, and then compare whether the next element of the pop-up sequence is still the same as the top of the stack.
That is, each time the elements of the pop-up sequence are compared with the elements at the top of the stack, the same will pop up, and the different will continue to put the elements on the stack. Finally, judge whether the stack is empty to determine whether it is a legal pop-up sequence.
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int pushIndex = 0;
int popIndex = 0;
while (pushIndex < pushed.length) {
stack.push(pushed[pushIndex]);
while (popIndex < popped.length
&& !stack.isEmpty()
&& popped[popIndex] == stack.peek()) {
stack.pop();
popIndex ++;
}
pushIndex ++;
}
return stack.isEmpty();
}
}
35. replication of complex linked list
Meaning: Interview question 35 Replication of complex linked list
Idea: besides the next pointer, the linked list also contains the random pointer. Use a Map to record the new node that has been created, and establish a mapping relationship between the old node and the new node. In the traversal process, you can directly get the created nodes from the Map.
class Solution {
Map<Node, Node> map = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
if (map.get(head) != null) {
return map.get(head);
}
Node newNode = new Node(head.val);
map.put(head, newNode);
newNode.next = copyRandomList(head.next);
newNode.random = copyRandomList(head.random);
return newNode;
}
}
41. median in data flow
Meaning: Interview question 41 Median in data stream
Idea: construct two heaps, a large root heap and a small root heap. Make the large root heap record the smaller part of the elements in the data flow, and the small root heap record the larger part of the elements in the data flow.
Make the values of the elements in the small root heap greater than those in the large root heap. Even if the root value of a small root heap is larger than that of a large root heap.
And ensure that when the number of data streams is even, the number of data in the two heaps is the same (at this time, the median is the average of the top elements of the two heaps). When the number of data streams is odd, the number of large root heap is one more than that of small root heap (at this time, the median is the top element of the large root heap).
class MedianFinder {
PriorityQueue<Integer> min;
PriorityQueue<Integer> max;
/** initialize your data structure here. */
public MedianFinder() {
min = new PriorityQueue();
max = new PriorityQueue(Collections.reverseOrder());
}
public void addNum(int num) {
if (max.size() == min.size()) {
min.add(num);
max.add(min.poll());
} else {
max.add(num);
min.add(max.poll());
}
}
public double findMedian() {
return max.size() == min.size() ? (max.peek() + min.peek()) / 2.0 : max.peek();
}
}
52. the first common node of two linked lists
Meaning: Interview question 52 The first common node of two linked lists
Idea: first calculate the length of the two linked lists. Calculate the difference diff between the lengths of the two linked lists. After a long linked list takes the diff step first, the two linked lists traverse backward at the same time until a common node is found or the end of the two linked lists is reached.
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
int lenA = len(headA);
int lenB = len(headB);
ListNode p = lenA > lenB ? headA : headB;
ListNode q = p == headA ? headB : headA;
int diff = Math.abs(lenA - lenB);
while (diff > 0) {
p = p.next;
diff--;
}
while (p != null && q != null) {
if (p == q) {
return p;
}
p = p.next;
q = q.next;
}
return null;
}
private int len(ListNode head) {
ListNode tmp = head;
int len = 0;
while (tmp != null) {
tmp = tmp.next;
len ++;
}
return len;
}
}
59-II Maximum value of the queue
Meaning: Interview questions 59 - II Maximum value of the queue
Idea: monotone stack. In addition to using a data queue to record queued elements, a double ended queue (monotonic) is used to maintain a decreasing sequence from beginning to end. The queue header element of a double ended queue is the maximum value of the queue. When entering the data queue, if the element is larger than the tail element of the double ended queue, the tail element should be out of the queue in turn, and then the current element should be inserted into the queue.
When the dequeued element of the data queue is equal to the header element of the double ended queue, the queue header element of the double ended queue should also be dequeued.
class MaxQueue {
Queue<Integer> queue;
Deque<Integer> maxValue;
public MaxQueue() {
queue = new LinkedList<>();
maxValue = new LinkedList<>();
}
public int max_value() {
if (maxValue.isEmpty()) {
return -1;
}
return maxValue.peek();
}
public void push_back(int value) {
queue.add(value);
while (!maxValue.isEmpty() && maxValue.getLast() < value) {
maxValue.removeLast();
}
maxValue.add(value);
}
public int pop_front() {
if (maxValue.isEmpty()) {
return -1;
}
int val = queue.poll();
if (val == maxValue.peek()) {
maxValue.removeFirst();
}
return val;
}
}