This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details
Pian if jing Hong, wan if you dragon. Rongyao Qiuju, Huamao Spring pine. This article was first published on the public account “Mushroom can’t sleep”, more exciting content welcome to pay attention to
1. Title Description
Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.
Example 1:
Input: head = [1,2,3,4,5], n = 2Copy the codeExample 2:
Input: head = [1], n = 1 output: []Copy the codeExample 3:
Input: head = [1,2], n = 1Copy the codeSz 1 <= sz <= 30 0 <= node. val <= 100 1 <= n <= sz
Ii. Analysis of Ideas:
This problem contains two questions: one is: how to find the penultimate NTH node; The second is how to delete a node. Let’s start with how to delete a node. In fact, it is very simple, that is, the next pointer to the node before the node to be deleted, pointing to the next node to be deleted. Node.next = node.next-next; Node is the front node of the node to be deleted. Let me tell you how to find the NTH node to the last. There are two main ways to do this:
- Double pointer method: define two fast and slow Pointers. The fast pointer takes N steps first, and then the fast and slow Pointers go back together until the fast pointer reaches the end of the linked list. In this case, the slow pointer is the leading node of the deleted pointer, and then I don’t have to say how to delete it.
- Use the stack: push the linked list onto the stack in order, and then start to eject elements. After eject elements N times, eject an element, which is the front node of the deleted node.
The next steps are to implement both methods using both sides of the code.
AC code
Method one:
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if (head == null) { return head; } ListNode ListNode = new ListNode(0, head); // ListNode fast = ListNode; // ListNode slow = ListNode; While (N > 0 && fast. Next! = null) { fast = fast.next; n --; } if (n > 0) { return listNode.next; } // While (fast. Next! = null) { fast = fast.next; slow = slow.next; } / / if the removed node is the first node from bottom, then directly set to null if (missile. The next = = null | | missile. Next, next = = null) {missile. Next = null; return listNode.next; } // Delete node slow.next = slow.next-next; return listNode.next; }}Copy the codeTime complexity :O(n), where n is the length of the list, traversing the linked table space once complexity :O(1).
Method 2:
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, Deque<ListNode> stack = new LinkedList<ListNode>(); ListNode cur = dummy; // Push in order while (cur! = null) { stack.push(cur); cur = cur.next; } for (int I = 0; i < n; ++i) { stack.pop(); ListNode prev = stack.peek(); ListNode prev = stack.peek(); ListNode prev = stack. Prev. next = prev.next-next; ListNode ans = dummy.next; return ans; }}Copy the codeTime complexity: O(n), where n is the length of the list, traversing the linked space once. Mainly the stack overhead
Four,
The overall difficulty of this question is ok. The difficulty is to know how to delete the node correctly, and how to find the deleted node correctly. In fact, there are many ways to delete a node, such as: assigning the value of the next node of the deleted node to yourself, and then deleting the next node of the deleted node can also achieve the desired effect.