Brooke

一、題目

Given the head of a linked list, remove the nth node from the end of the list and return its head.

 

Example 1:

 

 

 

 

 

 

Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1 Output: []

Example 3:

Input: head = [1,2], n = 1 Output: [1]

 

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

 

二、程式作法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
/*
解題思路：
使用兩個分別為快、慢速指針，
快速指針先行 n 個之後，再和慢速指針同步移動，
因此快速指針會先歷遍節點，此時慢速指針會指到要處理的節點
參考資料：
https://leetcode.com/problems/remove-nth-node-from-end-of-list/discuss/580393/C-one-pass-solution
*/
/*做法二*/
public class Solution
{
    public ListNode RemoveNthFromEnd(ListNode head, int n)
    {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;

        while (n > 0)
        {
            fast = fast.next;
            n--;
        }
        while (fast.next != null)
        {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return dummy.next;
    }
}

/*做法一*/
/*
public class Solution
{
    public ListNode RemoveNthFromEnd(ListNode head, int n)
    {
        int counter = 0;
        ListNode temp = head;
        while (temp != null)
        {
            counter++;
            temp = temp.next;
        }

        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode curr = dummy;

        int i = 0;
        while (i < counter - n)
        {
            curr = curr.next;
            i++;
        }
        curr.next = curr.next.next;

        return dummy.next;
    }
}
*/

 

三、思路筆記

目的為移除一串列的倒數第 n 個節點。

做法一，先來確認這串列的長度多大，再來找出該移除點，

並將其上一點的指標指向移除點的下一點。

做法二，此方法可改良讓求解時不用再歷串列到第二遍，

一開始宣告兩個「快、慢」指標，當題目要移除倒數第 n 個節點時，

我們就讓快指標先行 n 個節點，此時「快、慢」指標會差 n 個節點的距離，

兩個指標以此差距繼續同行，最後會造成的結果為，

當「快」指標指到結尾時(null)，「慢」指標也指到移除點了，

免去了串列不用再歷到第二遍。