我先用的第一种方法,先第一次遍历算出有节点数num,然后第二次遍历找到第num-n个节点,删除它的下一个节点,也就是第num-n节点.next = num-n节点.next.next(),然后需要注意的是找到第num-n个节点,指针需要从头节点移动num-n-1次,但是后来一直报空指针异常,我反复的检查,一步一步自己推,死活想不到,后来我直接把头节点的下一个删掉看看返回什么,才发现,示例中有一个只有一个节点的链表需要删除头节点,这样.next = .next.next当然就报错了,于是我把删除头节点的情况单独拿出来了,这是第一种方法的代码:
- class Solution {
- public ListNode removeNthFromEnd(ListNode head, int n) {
- ListNode h1 = head;
- ListNode h2 = head;
- int num =0;
- while(h1 != null){
- num++;
- h1=h1.next;
- }
- if(num == n){
- return head.next;
- }else{
- while(num - n-1 !=0){
- h2 = h2.next;
- num--;
- }
- h2.next = h2.next.next;
- }
- return head;
- }
- }
我记得我之前在剑指offer里面做过一道相同的题剑指offer22.链表中的倒数第k个节点_荔枝味啊~的博客-CSDN博客,我用的是双指针,就是第一个指针先走n步,然后第二个指针和第一个指针一起完后移动,当第一个指针为空的时候,第二个指针的位置就是要删除的节点,然后写了如下代码:
- class Solution {
- public ListNode removeNthFromEnd(ListNode head, int n) {
- ListNode h1 = head;
- ListNode h2 = head;
- if(h1.next == null)return head.next;
- while(n!=0){
- h1 = h1.next;
- n--;
- }
- h1 = h1.next;
- while(h1 != null){
- h1 = h1.next;
- h2 = h2.next;
- }
- h2.next= h2.next.next;
- return head;
- }
- }
三个示例过了但是我无法解决删除头节点的问题,于是就看题解了,题解是先创建了一个节点然后这个节点的下一个节点是头节点(其实我都没看到题目中有这个参数是val和next的构造方法),这样就很容易用.next = .next.next删除头节点了,这是题解代码和题目给出的ListNode的数据结构:
- /**
- * Definition for singly-linked list.
- * public class ListNode {
- * int val;
- * ListNode next;
- * ListNode() {}
- * ListNode(int val) { this.val = val; }
- * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
- * }
- */
- class Solution {
- public ListNode removeNthFromEnd(ListNode head, int n) {
- ListNode dummy = new ListNode(0, head);
- ListNode first = head;
- ListNode second = dummy;
- for (int i = 0; i < n; ++i) {
- first = first.next;
- }
- while (first != null) {
- first = first.next;
- second = second.next;
- }
- second.next = second.next.next;
- ListNode ans = dummy.next;
- return ans;
- }
- }
-