“This is the 10 days I participated in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

preface

I have been planning to learn data structures and basic algorithms, but I have seen them in fits and starts. Now I’m determined to stick to it. I’m going to start with LeetCode’s HOT100 and finish 1~2 exercises every day, hoping to develop the habit of continuous learning in this way. Because I am doing iOS development, mainly using Objective-C language, and I am also learning Swift recently, all the questions in this series will be solved using Swift language. What is updated in this paper is the NTH node from the bottom of the linked list deleted from question 10 019 of HOT100 in LeetCode.

The title

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 code

Example 2:

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

Example 3:

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

Tip:

The number of nodes in the linked list is sz 1 <= sz <= 30 0 <= node. val <= 100 1 <= n <= szCopy the code

Analysis of the

Delete the NTH node from the list and return the list. Therefore, double traversal can definitely solve the problem. The first traversal of the number of nodes in the statistical linked list, and then the second traversal for deletion can achieve the goal. The double loop is simple, but we can improve on it. The reason for the double loop is that we cannot count from the last node forward, and we do not know how many nodes there are in the linked list in advance, so we cannot locate the penultimate node. Therefore, if we traverse the linked list with two nodes fast and slow at the same time, the number of nodes between fast and slow is exactly N. So when fast reaches the end of the linked list, the slow node is exactly the NTH node from the bottom, so that we can find the target node through one traversal, and then carry out relevant deletion processing (here we need to consider whether the target node is the first node to be deleted). The overall idea is as follows:

1. Set virtual node dummyHead to point to head. 2. Set double-pointer fast and slow to start with dummyHead. Move fast until the number of elements separated from slow is n 4. Move fast and slow at the same time until fast points to last NULL 5. Point the next slow node to the next node (i.e. remove the target node) 6. Return next to dummyHeadCopy the code

Answer key

/** * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init() { self.val = 0; self.next = nil; } * public init(_ val: Int) { self.val = val; self.next = nil; } * public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }} * * /
class KLLC019 {
    func removeNthFromEnd(_ head: ListNode? ._ n: Int) -> ListNode? {
        // Output initialization
        var dummyHead = ListNode(-1)
        dummyHead.next = head
        var fast = dummyHead
        var slow = dummyHead
        // Move FAST back n nodes so that the distance between fast and slow is N
        for _ in 0..<n {
            fast = fast.next!
        }
        // Move fast and slow backwards at the same time until fast points to null, at which point slow's next is the target node to be deleted
        while fast.next ! = nil {
            fast = fast.next!
            slow = slow.next!
        }
        // Delete the target node
        slow.next = slow.next!.next
        // return the header
        return dummyHead.next
    }
}
Copy the code