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