Common interview questions of single linked list
- Find the number of effective nodes in the single linked list
- Find the penultimate node in the single lin k ed list (Sina)
- Reversal of single linked list (Tencent)
- 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
if (head.next == null) {
return null;
}
// First traversal: get the length of the linked list
int size = getLength(head);
// The second traversal: (size index) is the penultimate node
// data verification
if (index <= 0 || index > size) {
return null;
}
// Auxiliary variable
HeroNode cur = head.next;
// 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
- The head of the original linked list next = reverseHead.next
Code implementation:
// Reverse the single linked list
public static void reverseList(HeroNode head) {
// judge
if (head.next == null || head.next.next == null) {
return;
}
// Auxiliary variables (help traverse the original linked list)
HeroNode cur = head.next;
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
reverseHead.next = cur;//Link cur to the new linked list
cur = next;// Move back
}
// Put head Next points to reversehead Next, reverse
head.next = reverseHead.next;
}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
stack.add("jack");
stack.add("tom");
stack.add("smith");
//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>();
HeroNode cur = head.next;
// 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 class SingleLinkedListDemo {
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");
// Create linked list
SingleLinkedList singleLinkedList = new SingleLinkedList();
// Add according to mode 1:
// singleLinkedList.add(hero1);
// singleLinkedList.add(hero2);
// singleLinkedList.add(hero3);
// singleLinkedList.add(hero4);
// Add according to mode 2:
singleLinkedList.add2(hero1);
singleLinkedList.add2(hero4);
singleLinkedList.add2(hero2);
singleLinkedList.add2(hero3);
singleLinkedList.add2(hero3);
// display
singleLinkedList.list();
// modify
HeroNode newHeroNode = new HeroNode(2, "Xiao Lu", "Jade Unicorn~~~~~");
System.out.println("After modification:");
singleLinkedList.update(newHeroNode);
singleLinkedList.list();
// delete
singleLinkedList.dele(1);
System.out.println("After deletion:");
singleLinkedList.list();
// Get the number of valid nodes
System.out.println("Number of valid nodes=" + getLength(singleLinkedList.getHead()));
// Test the penultimate node
HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 1);
System.out.println(res);
HeroNode res1 = findLastIndexNode(singleLinkedList.getHead(), 2);
System.out.println(res1);
// Test the inversion of single linked list
System.out.println("Test linked list:");
singleLinkedList.list();
System.out.println("After reversal:");
reverseList(singleLinkedList.getHead());
singleLinkedList.list();
//Reverse order printing
System.out.println("Reverse order printing:");
reverseList(singleLinkedList.getHead());
singleLinkedList.list();
}
// 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>();
HeroNode cur = head.next;
// 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
if (head.next == null || head.next.next == null) {
return;
}
// Auxiliary variables (help traverse the original linked list)
HeroNode cur = head.next;
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
reverseHead.next = cur;// Link cur to the new linked list
cur = next;// Move back
}
// Put head Next points to reversehead Next, reverse
head.next = reverseHead.next;
}
// 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
if (head.next == null) {
return null;
}
// First traversal: get the length of the linked list
int size = getLength(head);
// The second traversal: (size index) is the penultimate node
// data verification
if (index <= 0 || index > size) {
return null;
}
// Auxiliary variable
HeroNode cur = head.next;
// 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
class SingleLinkedList {
// Initialize header node
private HeroNode head = new HeroNode(0, "", "");
// Return header node
public HeroNode getHead() {
return head;
}
public void setHead(HeroNode head) {
this.head = head;
}
// 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
public void add(HeroNode heroNode) {
// Auxiliary pointer
HeroNode temp = head;
// Loop traversal
while (true) {
// Find the end of the linked list
if (temp.next == null) {
break;
}
// Not found, move temp back
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
HeroNode temp = head;
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) {
HeroNode temp = head;
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
if (head.next == null) {
System.out.println("The linked list is empty");
return;
}
// Find the required node (auxiliary variable)
HeroNode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break;// Traverse the linked list
}
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);
}
}
// Display linked list
public void list() {
if (head.next == null) {
System.out.println("The linked list is empty");
return;
}
HeroNode temp = head.next;
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] Test linked list: 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]