19 Remove Nth Node From End of List 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)

Description:
Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

題目描述:
給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

示例 :

給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.

當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?1->2->3->5.

說明：

給定的 n 保證是有效的。

進(jìn)階：

你能嘗試使用一趟掃描實(shí)現(xiàn)嗎？

思路:

此題為 408原題

1. 先遍歷一次鏈表獲取長(zhǎng)度, 找到倒數(shù)第 n個(gè)結(jié)點(diǎn)的位置并移除, 需要遍歷兩次鏈表
2. 設(shè)置快慢指針, 快指針先移動(dòng) n個(gè)結(jié)點(diǎn), 然后快慢指針同步移動(dòng), 移除當(dāng)快指針為空時(shí)慢指針位置的結(jié)點(diǎn)即可, 只需要遍歷一次鏈表
   時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(1)

代碼:
C++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        if (!head or !head -> next) return nullptr;
        ListNode *fast = head, *slow = head;
        for (int i = 0; i < n; i++) fast = fast -> next;
        if (!fast) return head -> next;
        while (fast -> next) 
        {
            fast = fast -> next;
            slow = slow -> next;
        }
        slow -> next = slow -> next -> next;
        return head;
    }
};

Java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || head.next == null) return null;
        ListNode fast = head, slow = head;
        for (int i = 0; i < n; i++) fast = fast.next;
        if (fast == null) return head.next;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

Python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        p = q = dummy
        for i in range(n + 1):
            p = p.next
        while p:
            p, q = p.next, q.next
        q.next = q.next.next
        return dummy.next