Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to find the penultimate node of the linked list". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to find the penultimate node of the linked list.

What do you mean? Let's take the following linked list as an example:

Given the head node of the linked list, but do not know the actual length of the linked list, we are required to find the penultimate node of the linked list.

If you are looking for an element 1, if you are looking for 3, then you are looking for element 1:

How to use the queue? Xiao Hui's ideas are as follows:

1. Create a queue of length n, traverse the original linked list, and let the nodes enter the queue one by one:

two。 When the queue is full, let the elements at the end of the queue leave the team, and the new node joins the team:

3. When all the nodes in the linked list are traversed, the element at the end of the queue is the penultimate node (because the queue length is n):

-

First, we create two pointers P1 and P2 P1 pointing to the head node of the linked list, and P2 pointing to the nth node of the positive number of the linked list (that is, the third node in the example):

Next, we cycle the pointers P1 and P2 to the right at the same time, one step at a time, until pointer P2 moves to the end of the linked list:

At this point, because P2 points to the tail node of the linked list, and the distance between P1 and P2 is nMu1, the node P1 refers to is the penultimate node of the linked list we are looking for:

Obviously, this method only needs to traverse the linked list once from beginning to end, and uses only two pointers, and the space complexity of the algorithm is O (1).

Public class NthFromEnd {public static Node findNthFromEnd (Node head, int n) {Node p1 = head; Node p2 = head; / / move the p2 pointer to the nth node of a positive number for (int inode 1; I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.