Single chain surface test questions

class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;
    // Constructors 
    public HeroNode(int no, String name, Stirng nickname){
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
}

Sina interview questions --- Look up the last... In the single chain table k Nodes

Ideas ：

1. Write a method , Accept head node , Receive one at the same time index

2.index Means the last index node

3. First, traverse the list from beginning to end , Get the number of nodes in the linked list

4. obtain size after , Start traversing from the first node of the linked list , Traverse size-index Nodes

    //getLength() The method is to get the number of linked list nodes written by yourself 
public static HeroNode findLastIndexNode(heroNOde head, int index){
    if(head.next == null){
        return null;
    }
    int size = getLength(head);
    if(index <= 0 || index > size){
        return null;
    }
    heroNode cur = head.next;
    for(int i = 0; i < size - index; i++){
        cur = cur.next;
    }
    return cur;
}

Tencent interview questions --- Reverse the single chain table

Ideas

1. First define a node reverseHead = new HeroNode();

2. Go through the original list from beginning to end , Every time a node is traversed, it is taken out , And put it in the new list reverseHead The front end of

3. Of the original linked list head.next = reverseHead.next

public static void reversetList(HeroNode head){
    // If the current linked list is empty or there is only one node , Return directly without inversion 
    if(head.next == null || head.next.next ==null){
        return;
    }
    //
    HeroNode cur = head.next;
    HeroNode next = null; // The next node of the current node 
    HeroNode reversHead = new HeroNode(0,"","");
    While(cur != null){
    next = cur.next;
    cur.next = reverseHead.next;
    reverseHead.next = cur;
    cur = next;
    }
    head.next = reverseHead.next;
}

Baidu interview questions --- Print linked list from end to end

Ideas ：

The above requirement is to print the linked list in reverse order

If you reverse first and then print, the original linked list will be destroyed. It is not recommended

We can use the data structure of stack , Push each node into the stack , Use the stack's first in, last out feature to achieve reverse printing