Paste_Image.png
My code:
/**
* 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) {
if (head == null || n <= 0)
return null;
int count = 0;
boolean isN = false;
ListNode temp = head;
ListNode tempN = head;
while(temp != null) {
if (temp.next == null)
break;
if (isN)
tempN = tempN.next;
temp = temp.next;
count++;
if (count == n)
isN = true;
}
if (tempN.next == null)
head = null;
else if (count == n - 1)
head = head.next;
else
tempN.next = tempN.next.next;
return head;
}
}
My test result:
Paste_Image.png
这次作业比较简单，但如果按照他所说的， one pass就做出结果，就得动点脑子了。
方法就是 two pointer。 当前一个指针和链表相距 n 时，后一个指针就可以开始跟着前一个指针一个个得向前移动。最后前一个指针到头时，后一个指针就是该移除节点的位置。
当然会有一些细节需要考虑。
比如，链表只有一个节点，而 n = 1
链表有两个节点，而 n = 2
这几个细节考虑完后，就基本没问题了。
**
总结：前段时间和女朋友出去玩了一圈，但是时间太短，实在没有能力与心情去享受旅途。
这一年，将会发生太多事，如果我们能走下来，我一定会去她家看望她的父母。
但是，要走下来，真的好难。
我们一定要，一起走过去！
**
Anyway, Good luck, Richardo!
My code:
/**
* 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) {
if (head == null || n <= 0)
return head;
if (head.next == null)
return null;
ListNode curr = head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
int counter = 1;
while (counter < n) {
counter++;
curr = curr.next;
}
while (curr.next != null) {
curr = curr.next;
pre = pre.next;
}
pre.next = pre.next.next;
return dummy.next;
}
}
采用了 dummy code后就一切变得方便了。
为什么需要dummy node？
因为有的时候head是可以被处理的，比如删除。他也需要有一个头，指着他。
Anyway, Good luck, Richardo!
My code:
/**
* 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) {
if (head == null || n < 0) {
return null;
}
int total = 0;
ListNode temp = head;
while (temp != null) {
total++;
temp = temp.next;
}
n = total - n;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode curr = dummy.next;
ListNode pre = dummy;
int counter = 0;
while (curr != null) {
if (counter == n) {
pre.next = curr.next;
break;
}
else {
curr = curr.next;
pre = pre.next;
counter++;
}
}
return dummy.next;
}
}
two-pass
- 遍历一遍获得链表结点总数
- 删除
看了以前的解法才知道有更加简洁的做法。
重写一遍：
/**
* 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) {
if (head == null || n < 0) {
return null;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
int counter = 0;
ListNode curr = dummy.next;
ListNode pre = dummy;
ListNode post = curr;
while (post != null) {
post = post.next;
counter++;
if (counter == n) {
break;
}
}
if (counter < n) {
return dummy.next;
}
while (post != null) {
pre = pre.next;
curr = curr.next;
post = post.next;
}
pre.next = curr.next;
return dummy.next;
}
}
差不多的做法。
Anyway, Good luck, Richardo! -- 08/15/2016
