# JAVA data structure and algorithm -- single chain surface test questions (Sina, Baidu, Tencent)

## Common interview questions of single linked list

1. Find the number of effective nodes in the single linked list
2. Find the penultimate node in the single lin k ed list (Sina)
3. Reversal of single linked list (Tencent)
4. Print the single linked list from end to end (Baidu requires mode 1: reverse traversal. Mode 2: stack stack)

### Example 1: find the number of effective nodes

Idea:

• Method: obtain the number of effective nodes (if it is the linked list of the leading node, the head node needs not to be counted)
• Head is the head node and length is the number of valid nodes

Key code implementation:

```	public static int getLength(HeroNode head) {
if (head.next == null) {// Empty list judgment
return 0;
}
int length = 0;// Counter
HeroNode cur = head.next;// Auxiliary variable
while (cur != null) {// Header node not counted
length++;
cur = cur.next;// ergodic
}
return length;
}```

### Example 2: find the penultimate node in the single linked list

Idea:

• Write a method to accept the head node and an index at the same time
• index indicates the penultimate node
• First traverse the linked list from beginning to end to get the total length of the linked list getLength
• After getting the size, we start from the first one in the linked list to traverse the size index
• If found, the node will be returned; otherwise, null will be returned

Key code implementation:

```public static HeroNode findLastIndexNode(HeroNode head, int index) {
// Empty judgment: if the linked list is empty, null will be returned
return null;
}
// First traversal: get the length of the linked list
// The second traversal: (size index) is the penultimate node

// data verification
if (index <= 0 || index > size) {
return null;
}
// Auxiliary variable

// for loop positioning
for (int i = 0; i < size - index; i++) {
cur = cur.next;
}
return cur;

}```

### Example 3: inversion of single linked list

Idea: (Note: reverse node, not just data)

• First define a new node (reverseHead = new HeroNode())
• Traverse the original linked list from beginning to end. Every time you traverse a node, take it out and put it at the front of the new linked list

Code implementation:

```	// Reverse the single linked list
public static void reverseList(HeroNode head) {
// judge
return;
}
// Auxiliary variables (help traverse the original linked list)
HeroNode next = null;// Points to the next node of the current node [cur]
HeroNode reverseHead = new HeroNode(0, "", "");// New node
// Traverse the original linked list
while (cur != null) {
next = cur.next;// Temporarily save the next node of the current node
cur.next = reverseHead.next;// Point the next node of cur to the head node of the new linked list
cur = next;// Move back
}

}```

## Example 4: printing a single linked list from end to end

Idea:

Method 1: first reverse the single linked list and traverse it, such as example 3, but it is not recommended

Method 2: you can use the "stack" to press each node into the stack, and then use the first in and last out characteristics of the stack to achieve the effect of reverse printing

Stack knowledge supplement: first in then out

Test code (stack)

```package com.jun._3_linkedlist;

import java.util.Stack;

/**
* Use of test stack
* @author jun
*
*/
public class Test_Stack {

public static void main(String[] args) {
Stack<String> stack = new Stack();
//Push
//Out of stack
while(stack.size()>0) {
System.out.println(stack.pop());
}
}

}```

Stack output:

```smith
tom
jack```

Code implementation:

```	// Reverse order printing
public static void reversePrint(HeroNode head) {
if (head.next == null) {// Air judgment
return;
}
// Create a stack and push each node into the stack
Stack<HeroNode> stack = new Stack<HeroNode>();
// Press all nodes in the linked list
while (cur != null) {
stack.push(cur);
cur = cur.next;// cur moves back and pushes into the next node
}
// Traverse the nodes in the stack
while (stack.size() > 0) {
System.out.println(stack.pop());// First in then out
}

}```

## Complete code attached

```package com.jun._3_linkedlist;

import java.util.Stack;

/**
* Manage heroes through a single linked list
*
* @author jun
*
*/
public static void main(String[] args) {

// Create node
HeroNode hero1 = new HeroNode(1, "Song Jiang", "Timely rain");
HeroNode hero2 = new HeroNode(2, "Lu Junyi", "Jade Unicorn");
HeroNode hero3 = new HeroNode(3, "Wu Yong", "Zhiduoxing");
HeroNode hero4 = new HeroNode(4, "Lin Chong", "Leopard head");

// Add according to mode 1:
// Add according to mode 2:

// display

// modify
HeroNode newHeroNode = new HeroNode(2, "Xiao Lu", "Jade Unicorn~~~~~");
System.out.println("After modification:");

// delete
System.out.println("After deletion:");

// Get the number of valid nodes

// Test the penultimate node
System.out.println(res);
System.out.println(res1);

// Test the inversion of single linked list
System.out.println("After reversal:");

//Reverse order printing
System.out.println("Reverse order printing:");
}

// Reverse order printing
public static void reversePrint(HeroNode head) {
if (head.next == null) {// Air judgment
return;
}
// Create a stack and push each node into the stack
Stack<HeroNode> stack = new Stack<HeroNode>();
// Press all nodes in the linked list
while (cur != null) {
stack.push(cur);
cur = cur.next;// cur moves back and pushes into the next node
}
// Traverse the nodes in the stack
while (stack.size() > 0) {
System.out.println(stack.pop());// First in then out
}

}

// Reverse the single linked list
public static void reverseList(HeroNode head) {
// judge
return;
}
// Auxiliary variables (help traverse the original linked list)
HeroNode next = null;// Points to the next node of the current node [cur]
HeroNode reverseHead = new HeroNode(0, "", "");// New node
// Traverse the original linked list
while (cur != null) {
next = cur.next;// Temporarily save the next node of the current node
cur.next = reverseHead.next;// Point the next node of cur to the head node of the new linked list
cur = next;// Move back
}

}

// Find the penultimate node in the single linked list
/**
* Idea: 1. Write a method to accept the head node and an index at the same time. 2. Index represents the penultimate node
* 3,First, traverse the linked list from beginning to end to get the total length of the linked list getLength 4. After getting the size, we will traverse (size index) from the first one in the linked list
* 5,If found, the node will be returned; otherwise, null will be returned
*/
public static HeroNode findLastIndexNode(HeroNode head, int index) {
// Empty judgment: if the linked list is empty, null will be returned
return null;
}
// First traversal: get the length of the linked list
// The second traversal: (size index) is the penultimate node

// data verification
if (index <= 0 || index > size) {
return null;
}
// Auxiliary variable

// for loop positioning
for (int i = 0; i < size - index; i++) {
cur = cur.next;
}
return cur;

}

// Method: obtain the number of effective nodes (if it is the linked list of the leading node, the head node needs not to be counted)
// Head is the head node and length is the number of valid nodes
public static int getLength(HeroNode head) {
if (head.next == null) {// Empty list judgment
return 0;
}
int length = 0;// Counter
HeroNode cur = head.next;// Auxiliary variable
while (cur != null) {// Header node not counted
length++;
cur = cur.next;// ergodic
}
return length;
}

}

//Management hero
private HeroNode head = new HeroNode(0, "", "");

}

}

// The first way to add nodes
// Idea: when ranking number is not considered.
// 1. Find the last node of the current linked list
// 2. Point the next of the last node to the new node
// Auxiliary pointer
// Loop traversal
while (true) {
// Find the end of the linked list
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = heroNode;
}

// The second way to add heroes is to insert the specified position according to the ranking (if there is this ranking, the addition fails and a prompt is given)
public void add2(HeroNode heroNode) { // The temp you are looking for is the previous node in the add location
boolean flag = false;// Whether the ID number exists. The default value is false
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.no > heroNode.no) { // After temp is inserted, the position is found
break;
} else if (temp.next.no == heroNode.no) {
// Number exists
flag = true;
break;
}
temp = temp.next; // Move back, traverse
}
// Judge the value of false
if (flag) {
System.out.printf("number%d Save again, cannot join\n", heroNode.no);
} else {
// Insert into the linked list, after temp
heroNode.next = temp.next;
temp.next = heroNode;
}

}

// Delete node
// 1. The head cannot be moved, so the temp auxiliary node needs to find the previous node of the node to be deleted.
// 2. Temp is required for comparison next. no and the node to be deleted no for comparison
public void dele(int no) {
boolean flag = false;// Identifies whether the previous node of the node to be deleted is found
while (true) {
if (temp.next == null) {// You have reached the end of the linked list. Exit
break;
}

if (temp.next.no == no) {// Find the previous node temp of the node to be deleted
flag = true;
break;
}
temp = temp.next;// temp backward

}
// Judge flag
if (flag) {// find
temp.next = temp.next.next;

} else {
System.out.printf("Node to find%d， non-existent\n", no);
}
}

// Modify node information
public void update(HeroNode newHeroNode) {
// Air judgment
return;
}
// Find the required node (auxiliary variable)
boolean flag = false;
while (true) {
if (temp == null) {
}
if (temp.no == newHeroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
// Find the point to modify according to the flag
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {// Can't find
System.out.printf("No number found%d The node cannot be modified\n", newHeroNode.no);
}
}

public void list() {
return;
}
while (true) {
// judge
if (temp == null) {
break;
}
// Not null, output node information
System.out.println(temp);
// Move next backward
temp = temp.next;
}
}
}

//Define node
class HeroNode {
public int no;// Ranking order
public String name;// name
public String nickname;// alias
public HeroNode next;// Point to next node
// constructor

public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}

// Override toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}

}
```

## output

```No. 3 is saved and cannot be added
HeroNode [no=1, name=Song Jiang, nickname=Timely rain]
HeroNode [no=2, name=Lu Junyi, nickname=Jade Unicorn]
HeroNode [no=3, name=Wu Yong, nickname=Zhiduoxing]
HeroNode [no=4, name=Lin Chong, nickname=Leopard head]
After modification:
HeroNode [no=1, name=Song Jiang, nickname=Timely rain]
HeroNode [no=2, name=Xiao Lu, nickname=Jade Unicorn~~~~~]
HeroNode [no=3, name=Wu Yong, nickname=Zhiduoxing]
HeroNode [no=4, name=Lin Chong, nickname=Leopard head]
After deletion:
HeroNode [no=2, name=Xiao Lu, nickname=Jade Unicorn~~~~~]
HeroNode [no=3, name=Wu Yong, nickname=Zhiduoxing]
HeroNode [no=4, name=Lin Chong, nickname=Leopard head]
Number of valid nodes=3
HeroNode [no=4, name=Lin Chong, nickname=Leopard head]
HeroNode [no=3, name=Wu Yong, nickname=Zhiduoxing]
HeroNode [no=2, name=Xiao Lu, nickname=Jade Unicorn~~~~~]
HeroNode [no=3, name=Wu Yong, nickname=Zhiduoxing]
HeroNode [no=4, name=Lin Chong, nickname=Leopard head]
After reversal:
HeroNode [no=4, name=Lin Chong, nickname=Leopard head]
HeroNode [no=3, name=Wu Yong, nickname=Zhiduoxing]
HeroNode [no=2, name=Xiao Lu, nickname=Jade Unicorn~~~~~]
Test reverse printing
HeroNode [no=2, name=Xiao Lu, nickname=Jade Unicorn~~~~~]
HeroNode [no=3, name=Wu Yong, nickname=Zhiduoxing]
HeroNode [no=4, name=Lin Chong, nickname=Leopard head]```

Posted by lin on Sat, 21 May 2022 17:37:32 +0300