[LeetCode] 19. Remove Nth Node From End of List

轉自LeetCode

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

For 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.
Try to do this in one pass.

<Solution>

這題最難的地方是，題目要求只能 one pass

所以不能先歷遍一次，找出長度，再重新歷遍到訂位置刪除

這時候要用兩個指針來解決 (參考資料)

• curr 和 prv 一開始都指向 head

• 先移動 curr n步，如果 curr = NULL，代表 n 就是總長度，要刪除的就是 head，此時就回傳 head->next

• 如果 curr != NULL，此時同時移動 curr 和 prv，直到 curr 指到最後一個元素(curr->next = NULL)，這時候 prv 會指向要刪除元素的前一個元素，因此 prv->next = prv->next->next

code 如下

C++

Java


kotlin