0019-删除链表的倒数第N个节点

删除链表的倒数第N个节点

方案一

我们需要用两个指针来帮助我们解题，pre和cur指针。首先cur指针先向前走N步，如果此时cur指向空，说明N为链表的长度，则需要移除的为首元素，那么此时我们返回head->next即可，如果cur存在，我们再继续往下走，此时pre指针也跟着走，直到cur为最后一个元素时停止，此时pre指向要移除元素的前一个元素，我们再修改指针跳过需要移除的元素即可

借助单链表实现

C-源代码

#include <stdlib.h>

#include "LinkList.h"

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    
    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    dummy->next = head;
    
    struct ListNode *fast = dummy;
    struct ListNode *slow = dummy;
    
    for (int i = 1; i <= n + 1; i++) {
        fast = fast->next;
    }
    
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    
    struct ListNode *p = slow->next;
    slow->next = p->next;
    free(p);
    
    return dummy->next;
}

void test_0019(void) {
    int arr1[5] ={ 5, 4, 3, 2, 1 };
    struct ListNode *l1 = createNode(arr1, sizeof(arr1) / sizeof(arr1[0]));
    int n = 2;
    
    printNode(l1);
    
    struct ListNode *ret = removeNthFromEnd(l1, n);
    printNode(ret);
}

Swift实现

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        
        guard let head = head else {
            
            return nil
        }
        
        let dummy = ListNode(0)
        dummy.next = head
        var fast: ListNode? = dummy
        var slow: ListNode? = dummy
        
        // 设置快指针初始位置
        for _ in 0..<n {
            
            if fast == nil {
                
                break
            }
            fast = fast?.next
        }
        
        // 同时移动前后节点
        while fast != nil && fast?.next != nil {
            
            fast = fast?.next
            slow = slow?.next
        }
        
        // 删除节点
        slow?.next = slow?.next?.next
        
        return dummy.next
    }

参考Grandyang