The title

Delete the penultimate node of the linked list

Leetcode-cn.com/problems/re…

The public account “Java Programming Notes” record Java learning daily, share learning road dribs and drabs, from entry to give up, welcome to pay attention to

describe

Difficulty: Medium

Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.

** Advanced: ** Can you try using a scan implementation?

Example 1:

Enter: head = [1.2.3.4.5], n = 2Output:1.2.3.5]
Copy the code

Example 2:

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

Example 3:

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

Tip:

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

Solution

Double pointer solution

Their thinking

Very lucky, almost a success, recently prepared to brush more double pointer problem, do feel very interesting, nonsense not to say, today’s solution is the standard double pointer type

Given a linked list, delete the NTH node from the bottom of the list and return the head of the list

First, a linked list is given. The properties of linked lists cannot be explained much. Each node has a corresponding next node pointing to the next node

  • First of all, specify aPointer to the first, because it is a linked list, deleting N node only needs to change the pointing of the pointer before and after, and the first pointer basically does not move (except that N is the length of the current linked list, that is, deleting the first node), and can be directly returned at lastPointer to the firstCan be
  • The specifiedN a pointerIs the position of the reciprocal N node
  • The specifiedPointer to a cur, represents the current position of the traversal list, when next of the cur pointer isnull, indicating that the end of the list has been traversed
  • The bottomNSo we can start at the first node, we can figure out the N distance,N a pointerI’m pointing to the head at N distance,Pointer to a curPointing to the tail of distance N
  • In turn, movePointer to a cur.N a pointer, until next of the cur pointer is null, stopping traversal
  • Special treatment, whennThe value == the length of the linked list, that is, delete the first node and return it directlyhead.nextCan be

In terms of the position of the first node, calculate the distance N, where the N pointer points to the head of the N distance, and the cur pointer points to the tail of the N distance

Move the cur pointer. Move both the N pointer and the cur pointer as long as next is not null

Next of the cur pointer is null, i.e. the end of the list is traversed, and the node corresponding to the current N pointer is the node reciprocal of N

CODE

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } if(head.next ==null){ return null; }} * * /
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        	/ / pointer to the first
          ListNode res = head;
          //cur, the current list traverses the node
          ListNode cur = head;
          //N pointer to a node with the reciprocal of N
          ListNode nNode   = head;
          //PREN pointer to the first node of reciprocal N, used to delete N, pren. next = n.next
          ListNode preNNode   = head;
          // initialize with a cur pointer to the end of distance N
          for(int i =1; i<n ; i++){ cur = cur.next; }// Delete the first node and return head.next
          if(cur.next==null) {return res.next;
          }
					// Whether the current traversal reaches the tail
          while(cur.next! =null) {// The current node is assigned to preN
             preNNode = nNode;
            // the N pointer moves back
             nNode = nNode.next;
            //cur pointer moves back
             cur = cur.next;
          }
      		// Delete node N
          preNNode.next = nNode.next;
          returnres; }}Copy the code

The complexity of the

  • Time complexity:O(N), N is the length of the list
  • Space complexity:O(1)There is no memory space overhead other than the linked list itself

The results of

  • Execution time:0Ms, at allJavaDefeated in submission100.00% of the user
  • Memory consumption:36.1MB at allJavaDefeated in submission96.98% of the user

LeetCode:

LBWNB!!!!!!