This is the 9th day of my participation in the August Wen Challenge.More challenges in August

19, Remove Nth Node From End of List

The question:

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

Follow up: Could you do this in one pass?

Example 1:

Input: the head = [1, 2, 3, 4, 5], n = 2 Output:,2,3,5 [1]Copy the code

Example 2:

 Input: head = [1], n = 1
 Output: []
Copy the code

Example 3:

 Input: head = [1,2], n = 1
 Output: [1]
Copy the code

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Problem solving:

1. Cache + object reference

Iterate through the linked list and take the position in the list as the key, and the linked list itself as the value in the map. After completion of the traversal, the length of the linked list itself can be known. At this time, we can take out the penultimate N+1 and N nodes in O (1) time complexity. At this point, we will point next to the NTH +1 node to the next node of the NTH node.

     /** * The traversal node is placed in the cache, and the number of traversals is counted during the traversal process, and then read from the cache for processing */
     public static ListNode removeNthFromEndCache(ListNode head, int n) {
         // Walk through the linked list and store the nodes in the map
         Map<Integer, ListNode> map = new HashMap<>();
         ListNode cursor = head;
 ​
         int size = 0;
         while(cursor ! =null) {
             map.put(++size, cursor);
             cursor = cursor.next;
         }
         // Get the total length of the list
         int targetIndex = size - n + 1;
         if (targetIndex == 1) {
             head = head.next;
         } else {
             map.get(targetIndex - 1).next = map.get(targetIndex).next;
         }
 ​
         return head;
     }
Copy the code
2, fast and slow pointer method

How Pointers, as shown in the figure, making quick pointer go N nodes and then began to move slowly pointer, subsequent both moving at the same speed, fast pointer to tail slow pointer in the NTH node position from bottom, known from the NTH node, a node before processing to the next node to problem solving.

     The fast pointer takes n steps first, and the slow pointer and the fast pointer move synchronously. When the fast pointer reaches the end, it takes n more steps than the slow pointer, and the slow pointer is exactly N */ away from the end
     public static ListNode removeNthFromEndTwoPointer(ListNode head, int n) {
         // Define the speed pointer
         ListNode fast = head, slow = head;
         for (int i = 0; i < n; i++) {
             fast = fast.next;
         }
         if (fast == null) {
             return slow.next;
         }
 ​
         while(fast.next ! =null) {
             fast = fast.next;
             slow = slow.next;
         }
         slow.next = slow.next.next;
 ​
         return head;
  }
Copy the code