[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++

	/**
	* 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 == NULL) {
	return NULL;
	}
	ListNode *curr = head;
	ListNode *prv = head;
	//> move curr n steps
	for(int i = 0; i < n; i++) {
	if(!curr) {
	return head->next;
	}
	curr = curr->next;
	}
	//> if curr = NULL
	//> then n is the length of the list
	//> delete the head
	if(curr == NULL) {
	return head->next;
	}
	//> move curr and prv in the same time
	//> until curr->next is NULL
	while(curr->next) {
	curr = curr->next;
	prv = prv->next;
	}
	//> prv point to the previous element
	//> before the element which is going to be deleted
	prv->next = prv->next->next;
	return head;
	}
	};

view raw removeNthNodeFromEndOfList.cpp hosted with ❤ by GitHub

Java

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public ListNode removeNthFromEnd(ListNode head, int n) {
	ListNode front = head;
	ListNode back = head;
	while(n > 0) {
	front = front.next;
	--n;
	}
	while(front != null && front.next != null) {
	front = front.next;
	back = back.next;
	}
	if (front == null) {
	return head.next;
	}
	back.next = back.next.next;
	return head;
	}
	}

view raw removeNthNodeFromEndOfList.java hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var li = ListNode(5)
	* var v = li.`val`
	* Definition for singly-linked list.
	* class ListNode(var `val`: Int) {
	* var next: ListNode? = null
	* }
	*/
	class Solution {
	fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
	var left = head
	var right = head
	IntRange(1,n).forEach {
	right = right?.next
	}
	while(right?.next != null) {
	left = left?.next
	right = right?.next
	}
	return if(right == null) {
	head?.next
	} else {
	left?.next = left?.next?.next
	head
	}
	}
	}

view raw remove_nth_node_from_end_of_list.kt hosted with ❤ by GitHub