删除链表的倒数第N个节点

待我称王封你为后i 2021-06-10 20:38 342阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzk2ODYxMw_size_16_color_FFFFFF_t_70][]

class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode p = head;
            int i;
            for(i = 0; i < n; i++) //用于判断链表长度
            {
                p = p.next;
                if(p == null)
                    break;
            }
            if(i == n - 1 && p ==null) //链表长度为n时，删除头结点
                return head.next;
            if(i < n - 1 && p == null) //如果链表长度小于n，则返回原链表
                return head;
            ListNode q = head;
            while(p.next != null)
            {
                p = p.next;
                q = q.next;
            }
            q.next = q.next.next;
            return head;
        }
    }

###  思路： ###

因为删除头结点的情况是特殊的，那么就对这种情况特殊处理，如果删除的是头结点（链表长度l等于倒数第n个），则返回head.next。其余正常情况则当前面的指针走到最后时，q.next = q.next.next;

### 他山之石： ###

class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            if (head == null) {
                return null;
            }
    
            ListNode dummyHead = new ListNode(-2);
            dummyHead.next = head;
            ListNode fast = dummyHead;
            ListNode slow = dummyHead;
    
            for (int i = 0; i < n; i++) {
                fast = fast.next;
            }
    
            while (fast.next != null){
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
    
            return dummyHead.next;
        }
    }

让两个“指针”一起向前遍历时，有个特殊情况就是要删除头结点，该方法在最前面新增一个模拟结点，让原链表的头结点变为第二个结点，使得特殊的问题一般化，从而解决。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzk2ODYxMw_size_16_color_FFFFFF_t_70]: /images/20210518/45c6c0076ddb450eab1e6d3bd2846984.png