初级算法-链表-删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

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

摘一个示例做个说明.
示例 1：
如图
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

条件分析:

1. 链表删除某一项 -> 需要找到删除的位置
2. 返回链表的头结点 -> 返回删除后的链表

解决思路1:

1. 根据分析1,说明需要找到删除节点的位置
2. 根据分析2,说明需要知道链表的长度

先判断删除的是否是头节点,然后通过循环找到需要删除的位置,再进行循环操作指到需要删除的节点,让节点指向待删除节点的下一个节点.

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    let index = nodeLength(head) - n
    
    if index == 0 {
        // 删除第一个
        return head?.next
    }
    
    var newHead = head
    for _ in 0 ..< index - 1 {
        newHead = newHead?.next
    }
    newHead?.next = newHead?.next?.next
    
    return head;
}

func nodeLength(_ head: ListNode?) -> Int{
    
    if head == nil {
        return 0
    }
    // 通过递归获取长度
    return nodeLength(head?.next) + 1
}

删除链表的倒数第N个节点 1 提交结果.jpg

解决思路2:

1. 根据分析1,说明可以采用快慢指针,先让快指针指向n节点的位置,然后同时让快慢指针移动,直到快指针指向链表末尾.
2. 根据分析2,此时慢指针指向的就是倒数第n个节点,直接让慢指针指向下一个节点即可.

创建一个节点,然后让该节点指向链表头节点.然后定义快慢指针,让快指针先移动n位,然后保持快慢指针相差n,当快指针指向末尾的时候,慢指针指向倒数第n个节点.最后让慢指针指向删除的下一个节点即可.

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    let resultHead = ListNode(-1)
    resultHead.next = head
    var fast = resultHead
    var slow = resultHead
    
    for _ in 0 ..< n {
        // 先让快指针指向第n个节点
        fast = fast.next!
    }
    
    while fast.next != nil {
        // 让快慢指针同时指向下一个节点,直到链表结束,此时快慢指针相差n个
        fast = fast.next!
        slow = slow.next!
    }
    // 让慢指针指向下一个节点即可
    slow.next = slow.next!.next
    
    return resultHead.next
}

删除链表的倒数第N个节点 2提交结果.jpg

解决思路3:

解决思路2优化,还是快慢指针,还是快指针先走,不同与思路2先循环,采用变量判断是否需要让慢指针移动.

一趟扫描,通过哨兵,实现删除.

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    let resultHead = ListNode(-1)
    resultHead.next = head
    var fast = resultHead, slow = resultHead, index = 0
    while fast.next != nil {
        // 让快慢指针同时指向下一个节点,直到链表结束,此时快慢指针相差n个
        fast = fast.next!
        index += 1
        if index > n {
            slow = slow.next!
        }
    }
    // 让慢指针指向下一个节点即可
    slow.next = slow.next!.next
    
    return resultHead.next
}

删除链表的倒数第N个节点 3提交结果.jpg

测试用例:

let endNode = ListNode.init(0)
let fourNode = ListNode.init(1)
fourNode.next = endNode
let threeNode = ListNode.init(2)
threeNode.next = fourNode
let secondNode = ListNode.init(3)
secondNode.next = threeNode
let firstNode = ListNode.init(4)
firstNode.next = secondNode
let headNode = ListNode.init(5)
headNode.next = firstNode

考察要点:

• 链表
• 双指针