首页 > 代码库 > Leetcode: Remove Nth Node From End of List

Leetcode: Remove Nth Node From End of List

两次通过,考虑漏了一种情况:input: {1}, 1, 这种情况的output是null,应特殊处理; 同时,另外一个问题是:当要被删除的元素是最后一个元素的时候,我的方法又只能从头找起,不够简洁

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode removeNthFromEnd(ListNode head, int n) {
14         ListNode current = head;
15         ListNode runner = head;
16         while (n > 1){
17             runner = runner.next;
18             --n;
19             if (runner == null) return head;
20         }
21         while (runner.next != null){
22             runner = runner.next;
23             current = current.next;
24         }
25         if (current.next != null){
26             current.val = current.next.val;
27             current.next = current.next.next;
28             return head;
29         } 
30         else{ // special case when n=1
31             runner = head;
32             if (runner == current) return null; //special case when n=1 and the list has only one element
33             while (runner.next != current){
34                 runner = runner.next;
35             }
36             runner.next = runner.next.next;
37         }
38         return head;
39     }
40 }

我这次做的太麻烦了,贴个别人简单的做法,有时候,做一个dummy node,它的next指向head是一个好办法:

 1 public class Solution {
 2     public ListNode removeNthFromEnd(ListNode head, int n) {
 3         // Start typing your Java solution below
 4         // DO NOT write main() function
 5 
 6         ListNode dummy = new ListNode(0);
 7         dummy.next = head;
 8         ListNode p = dummy;        
 9         ListNode q = dummy;
10         for(int i=0;i<n+1;i++){   // With n+1, when q reaches the end of the list, q is at the one before the to-delete node.
11             q = q.next;
12         }
13         while(q!=null){
14             p = p.next;
15             q = q.next;
16         }
17         p.next =p.next!=null?p.next.next:null;
18         return dummy.next;       
19     }
20 }