剑指 Offer II 021. 删除链表的倒数第 n 个结点

最直接的思路 求出来长度 在特殊处理下只有一个元素 和要删除的元素和长度相等的情况

截屏2022-04-13 下午7.09.21.png

看着还行的样子。。

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {

        var count = 0
        var tempHead = head
        let endHead = head

        while tempHead != nil {
            
            count += 1
            tempHead = tempHead?.next
        }
         if count == 1 {
            return nil
        }
        if count == n  {
            return head?.next
        }

        var dHead = endHead
        
        for i in 0..<count{
            
            if i == ( count - 1 - n ){
                dHead?.next = dHead?.next?.next
                break
            }
            dHead = dHead?.next
        }
        return endHead
    }

双指针。，。 既然是倒数的 那么一开始的时候。两个指针都指向起始位置
然后指针之间的间隔是2的话。一起移动指针 那么当右边的指针走到最右边的时候 左边的指针就是倒数第2个节点
就可以不用管总长度了。。

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        
        
        var tempHead = head
        let endHead = head
        var right = 0
        
        var dHead = endHead

        while tempHead != nil {
            
            if right >= n + 1 {

                dHead = dHead?.next
            }
            tempHead = tempHead?.next
            right += 1

        }
        //说明移除的是第一个
        if right == n {
            
            return head?.next
        }
        
        if right == 1 {
            
            return nil
        }
        
        dHead?.next = dHead?.next?.next

        return endHead
        
    }

然后使用虚拟头 解决要删除的是头结点的情况

    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        
        if head == nil {
            return head
        }
        
        var fast = head
        var slow: ListNode? = ListNode(-1, head)
        let h = slow
        var right = 0
        
        while fast != nil {
               
               if right >= n   {

                   slow = slow?.next
               }
               fast = fast?.next
               right += 1
           }
        
        
        slow?.next = slow?.next?.next
        
        return h?.next

       
        
    }