Skip to content

LeetCode: 19-Remove Nth Node From End of List 解題紀錄

Last Updated on 2021-02-07 by Clay

題目

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

Follow up: Could you do this in one pass?

Example:

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

本題給定一個鏈結串列（Linked List），而我們要做的，便是將倒數第 n 個元素刪除，並回傳刪除後的 Linked List。

解題思路

我的想法：

  • 建立兩個指向 head 的指標
  • 讓其中一個先走 n 步
  • 兩個指標同時走；當第一個指標先走完了輸入的鏈結串列，即停止
  • 將第二個指標指向節點的下一個節點略過
  • 當需要略過的節點是第一個元素時，直接使用 head->next 回傳


C++ 程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // Preventation
        if (head->next == NULL) {
            return NULL;
        }
        
        // Init
        ListNode *currentNode = new ListNode(0, head);
        ListNode *removeNode = new ListNode(0, head);
        int length = 0;
        
        // Walk
        while (currentNode->next->next != NULL) {
            ++length;
            if (length <= n) {
                currentNode->next = currentNode->next->next;
            }
            else {
                currentNode->next = currentNode->next->next;
                removeNode->next = removeNode->next->next;
            }
        }

        // If remove node is the first node
        if (n-length == 1) {
            return head->next;
        }
        // Remove other node
        else {
            removeNode->next->next = removeNode->next->next->next;
            return head;
        }
    }
};


Python 程式碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # Preventation
        if head.next == None: return None
        
        # Init
        currentNode = ListNode(0, head)
        removeNode = ListNode(0, head)
        length = 0
        
        # Walk
        while (currentNode.next.next != None):
            length += 1
            if length <= n:
                currentNode.next = currentNode.next.next
            else:
                currentNode.next = currentNode.next.next
                removeNode.next = removeNode.next.next
        
        # If remove node is the first node
        if n-length == 1:
            return head.next
        # Remove other node
        else:
            removeNode.next.next = removeNode.next.next.next
            return head


References

Tags:

Leave a Reply