Shulou(Shulou.com)05/31 Report--

This article mainly introduces "how C++ can remove the penultimate node of the linked list". In daily operation, I believe many people have doubts about how C++ can remove the penultimate node of the linked list. I have consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts of "how C++ can remove the penultimate node of the linked list". Next, please follow the editor to study!

Remove Nth Node From End of List removes the penultimate node of the linked list

Given a linked list, remove the nth node from the end of list and return its head.

For example

Given linked list: 1-> 2-> 3-> 4-> 5, and n = 2.

After removing the second node from the end, the linked list becomes 1-> 2-> 3-> 5.

Note:

Given n will always be valid.

Try to do this in one pass.

This problem allows us to remove the penultimate node of the linked list, defining that n must be valid, that is, n will not be greater than the total number of elements in the linked list. There are also topics that require a traversal to solve the problem, so you have to think of some more ingenious ways. For example, the first thing to consider is how to find the penultimate node. Since only one traversal is allowed, the number of elements in the linked list cannot be counted with a complete traversal, but should be removed when traversing to the corresponding position. Then you need to use two pointers to help solve the problem, pre and cur pointers. First, the cur pointer takes N steps forward. If cur points to null at this time, indicating that N is the length of the linked list, then the first element to be removed can be removed. Then return head- > next at this time. If cur exists, continue to go down, and the pre pointer will follow until cur is the last element. At this time, pre points to the previous element to be removed, and then modify the pointer to skip the element to be removed. See the code below:

Method 1:

Class Solution {public: ListNode* removeNthFromEnd (ListNode* head, int n) {if (! head- > next) return NULL; ListNode* pre = head, * cur = head; for (int I = 0; I

Next; if (! cur) return head- > next; while (cur- > next) {cur = cur- > next; pre = pre- > next;} pre- > next = pre- > next- > next; return head;}}

Method 2:

Class Solution {public: int getLength (ListNode* head) {int length = 0; while (head) {+ + length; head = head- > next;} return length;} ListNode* removeNthFromEnd (ListNode* head, int n) {ListNode* dummy = new ListNode (0, head); int length = getLength (head); ListNode* cur = dummy For (int I = 1; I

Next;} cur- > next = cur- > next- > next; ListNode* ans = dummy- > next; delete dummy; return ans;}}; at this point, the study on "how C++ removes the penultimate node of the linked list" is over. I hope I can solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.