Directory:

• Valid data in a singly linked list
• Single linked list data inversion
• Reverse data without changing the original data

In this article, we will analyze the common interview questions on the single linked list.

Valid data in a singly linked list

Effect:

The final valid data result is: 5

Code implementation:

// The number of valid single-linked lists
    public int linkedLength(HeroNode head) {

        int length = 0;

        while(head.next ! =null) {
            length++;
            head = head.next;
        }
        return length;
    }
Copy the code

Conclusion:

• Pass in the header node, loop through all the data in the header node, and record it through the length identifier

Single linked list data inversion

Effect:

First analysis:

• 1. Traverse all data of the head node
• 2. Add node data to the secondary reverseHead by using a secondary reverseHead node

I may say this with a stiff edge. Look at the picture and speak!

Auxiliary graph:

Second analysis:

• 1. In order to complete the single-linked list inversion, the valid element in the single-linked list must be >= 2, otherwise there is no need to reverse only one element
• 2. Finally, the original head node points to the next position of the reverseHead to complete the reverse of the single linked list

Concrete implementation:

    // Single-linked list inversion
    public void reversal(HeroNode head) {
        // List number <=0 cannot be reversed
        if (head.next == null || head.next.next == null) {
            return;
        }

        // Define auxiliary traversal. Walk me through the old list
        HeroNode temp = head.next;

        // Indicates the next node of the current node
// HeroNode next = null;

        // Reverse the node
        HeroNode reverseHead = new HeroNode(0.""."");

        // Iterate over the original list once and place it into the reverseHead
        while(temp ! =null) {
            // Save the next node of the current node (next is the secondary node)
            HeroNode next = temp.next;

            // Point the next node of cur to the head of the new list
            temp.next = reverseHead.next;

            // Connect cur to the new linked list
            reverseHead.next = temp;

            // make cur point to the next node
            temp = next;
        }

        // point head.next to reversehead.next
        head.next = reverseHead.next;
    }
Copy the code

Use:

        linkedList.add(new HeroNode(1."Sung river"."Timely rain"));
        linkedList.add(new HeroNode(5."Qin Ming"."Thunderfire"));
        linkedList.add(new HeroNode(6."Wood into"."Little cyclone"));
        linkedList.add(new HeroNode(3."吴用"."Resourceful"));
        linkedList.add(new HeroNode(2."李逵".Black Tornado));
        
         linkedList.show();

        linkedList.reversal(linkedList.head);

        System.out.println("The inverted result is :");
        linkedList.show();  
Copy the code

The running results are as follows:

HeroNode{no=1, name='sung river', nickName='Timely rain'}
HeroNode{no=5, name='qin Ming', nickName='Thunderfire'}
HeroNode{no=6, name='wood into', nickName='Little cyclone'}
HeroNode{no=3, name='with wu', nickName=Resourcefulness}
HeroNode{no=2, name='李逵', nickName=Black Cyclone} HeroNode{no=2, name='李逵', nickName=Black Cyclone}
HeroNode{no=3, name='with wu', nickName=Resourcefulness}
HeroNode{no=6, name='wood into', nickName='Little cyclone'}
HeroNode{no=5, name='qin Ming', nickName='Thunderfire'}
HeroNode{no=1, name='sung river', nickName='Timely rain'}
Copy the code

Diagram understanding:

Reverse data without changing the original data

The final effect picture:

Analysis:

• Reverse data without changing the original data, using the above method can also be directly done, knowledge finally do not take the original data head node to point to the changed node, but this method is not good to use, next to introduce the use of Stack(Stack)

Use of the Java Stack() Stack

Illustration:

Use of the Java Stack() Stack

Complete code:

// Print data in reverse order without changing the original data
    public void reversal2(HeroNode head) {

        HeroNode temp = head;

        Stack<HeroNode> heroNodeStack = new Stack<>();


        while(temp.next ! =null) {
            heroNodeStack.add(temp.next);
            temp = temp.next;
        }

        while (heroNodeStack.size() > 0) {
            System.out.println("The inversion data is :"+heroNodeStack.pop()); }}Copy the code

Use:

        System.out.println("The original data is :");

        initData(linkedList);
        linkedList.show();

        System.out.println("Print the data backwards without changing the original data :");
        linkedList.reversal2(linkedList.head);

        System.out.println("The original data is :");
        linkedList.show();
Copy the code

The running results are as follows:

The original data is HeroNode{no=1, name='sung river', nickName='Timely rain'}
HeroNode{no=5, name='qin Ming', nickName='Thunderfire'}
HeroNode{no=6, name='wood into', nickName='Little cyclone'}
HeroNode{no=3, name='with wu', nickName=Resourcefulness}
HeroNode{no=2, name='李逵', nickName=Black Cyclone} Do not change the original data, print the data backwards: reverse data :HeroNode{no=2, name='李逵', nickName=Black Cyclone} Reverse data :HeroNode{no=3, name='with wu', nickName=Resourcefulness} Reverse data :HeroNode{no=6, name='wood into', nickName='Little cyclone'} Reverse data :HeroNode{no=5, name='qin Ming', nickName='Thunderfire'} Reverse data :HeroNode{no=1, name='sung river', nickName='Timely rain'} The original data is HeroNode{no=1, name='sung river', nickName='Timely rain'}
HeroNode{no=5, name='qin Ming', nickName='Thunderfire'}
HeroNode{no=6, name='wood into', nickName='Little cyclone'}
HeroNode{no=3, name='with wu', nickName=Resourcefulness}
HeroNode{no=2, name='李逵', nickName=Black Cyclone}
Copy the code

The complete code

What do you like?

Data structures and algorithms directory

Original is not easy, your praise is my biggest support ~