【数据结构与算法】之深入解析“删除链表的倒数第N个结点”的求解思路与算法示例

一、题目要求

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

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

  

 

  
1
  
2
 

• 示例 2：

输入：head = [1], n = 1
输出：[]

  

 

  
1
  
2
 

• 示例 3：

输入：head = [1,2], n = 1
输出：[1]

  

 

  
1
  
2
 

• 提示：
• • 链表中结点的数目为 sz；
• • 1 <= sz <= 30；
• • 0 <= Node.val <= 100；
• • 1 <= n <= sz。

二、求解算法

① 双指针

• 题目要求删除倒数的第 n 个节点，可以先让快指针先走 n 步，接着快慢指针一起向前走，知道快指针指向尾部，这样慢指针之后的就是要删除的：

• 定义虚拟的头节点，这样都链表中所有的节点都是一样的操作；
• 定义两个指针分别是 fast 和 slow；
• 先让 fast 指针走 n+1 步，这样做的目的是以后 fast 指针指向链表尾部为空的时候，slow 指针正好指向要删除的节点前面的节点；
• 让快慢指针一起运动，直到快指针指向空；
• 删除慢指针后面的元素，返回虚拟头节点的下一个元素即可。
• Swift 示例：

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    guard head?.next != nil else {
        if head == nil || n == 1 {
            return nil
        } else {
            return head
        }
    }
    
    var count = 1
    var current = head
    var toDeletePre: ListNode?
    while current?.next != nil {
        current = current?.next
        count += 1
        if count == n + 1 {
            toDeletePre = head
        } else if count > n + 1 {
            toDeletePre = toDeletePre?.next
        }
    }
    
    if count == n {
        return head?.next
    }
    
    if toDeletePre != nil {
        toDeletePre?.next = toDeletePre?.next?.next
    }
    return head
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
 

• Java 示例：

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyhead = new ListNode(-1,head);

        ListNode fast = dummyhead;
        ListNode slow = dummyhead;

        for(int i = 0; i <= n; ++i){
            if(fast != null)
                fast = fast.next;
        }
        while (fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummyhead.next;
    }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

② 计算链表长度（LeetCode官方解法）

• 一种容易想到的方法是，首先从头节点开始对链表进行一次遍历，得到链表的长度 L。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L−n+1 个节点时，它就是我们需要删除的节点。
• 为了与题目中的 n 保持一致，节点的编号从 1 开始，头节点为编号 1 的节点。
• 为了方便删除操作，可以从哑节点开始遍历 L−n+1 个节点。当遍历到第 L−n+1 个节点时，它的下一个节点就是需要删除的节点，这样只需要修改一次指针，就能完成删除操作。

• C++ 示例：

class Solution {
public:
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode* cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

• Java 示例：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

文章来源: blog.csdn.net，作者：Serendipity·y，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/Forever_wj/article/details/122548202