【JAVA、C++】LeetCode 019 Remove Nth Node From End of List

Given a linked list, remove the n^th 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.

解题思路一：

先计算length，然后删除

JAVA实现：

static public ListNode removeNthFromEnd(ListNode head, int n) {
		if(n<=0)
			return head;
		ListNode ln=head;
		int i=1;
		while(ln.next!=null){
			ln=ln.next;
			i++;
		}
		if(i==n)
			return head.next;
		ln=head;
		for(;i>n+1;i--)
			ln=ln.next;
		ln.next=ln.next.next;
		return head;
	}

解题思路二：

一个指针先走n步，另一个指针跟上。

C++：

 1 class Solution {
 2 public:
 3     ListNode* removeNthFromEnd(ListNode* head, int n) {
 4         if (n <= 0)
 5             return head;
 6         ListNode* cur = head;
 7         for (int i = 0; i < n-1; i++) {
 8             if (cur->next != NULL)
 9                 cur = cur->next;
10             else return head;
11         }
12         if (cur->next == NULL) {
13             ListNode*temp = head;
14             head = head->next;
15             delete temp;
16             return head;
17         }
18         cur = cur->next;
19         ListNode* cur2 = head;
20         while (cur->next != NULL) {
21             cur2 = cur2->next;
22             cur = cur->next;
23         }
24         cur = cur2->next;
25         cur2->next = cur->next;
26         delete cur;
27         return head;
28     }
29 };