题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解题思路

由于单向链表没有指向前一个节点的指针，所以如果要删除倒数第N个节点，我们就必须先遍历一次链表，记录链表的长度，再遍历删除。

解法1

转换思路

我们可以先将链表反转，这样一来题目就等于变成了删除正数第N个节点，那我们就可以直接遍历到第N个节点，然后原地删除，最后只需要再将链表反转回来即可。

public class Code {
       public static void main(String[] args) {
           Code c = new Code();        ListNode n = new ListNode(1);        ListNode head = n;        for (int i = 2; i < 6; i++) {
               n.next = new ListNode(i);            n = n.next;        }        System.out.println(c.removeNthFromEnd(head, 1));    }    public ListNode removeNthFromEnd(ListNode head, int n) {
           //基本校验        if(head == null || n < 1){
               return null;        }        //反转链表        ListNode pre = null;        ListNode cur = head;        while (cur != null) {
               ListNode next = cur.next;            cur.next = pre;            pre = cur;            cur = next;        }        //如果是要删除最后一个节点，则无需遍历，直接指向next即可        if (n == 1) {
               pre = pre.next;        } else {
               //找到要删除指定节点            ListNode pNode = null;            ListNode cNode = pre;            for (int i = 0; i < n - 1; i++) {
                   pNode = cNode;                cNode = cNode.next;            }            //删除            pNode.next = cNode.next;        }        //再反转回来        ListNode pre2 = null;        ListNode cur2 = pre;        while (cur2 != null) {
               ListNode next = cur2.next;            cur2.next = pre2;            pre2 = cur2;            cur2 = next;        }        return pre2;    }}

解法2

双指针法，类似快慢指针的道理，让第一个指针先走n步，然后再和第二个指针一起走，当第一个指针走到底时，第二个指针刚好来到n位置

public class Code {
       public static void main(String[] args) {
           Code c = new Code();        ListNode n = new ListNode(1);        ListNode head = n;        for (int i = 2; i < 3; i++) {
               n.next = new ListNode(i);            n = n.next;        }        System.out.println(head);        System.out.println(c.removeNthFromEnd(head, 1));    }    public ListNode removeNthFromEnd(ListNode head, int n) {
           //设置一个哑节点，方便处理边界问题        ListNode dummy = new ListNode(-1);        dummy.next = head;        //第一个指针        ListNode fNode = head;        //让第一个指针先走n步        for (int i = 0; i < n; i++) {
               fNode = fNode.next;        }        //第二个指针        ListNode sNode = dummy;        //然后两个指针在一起走，当第一个指针走完的时候，第二个指针刚好走到了n的前一个位置        while (fNode != null) {
               sNode = sNode.next;            fNode = fNode.next;        }        //删除n位置的节点        sNode.next = sNode.next.next;        //返回        return dummy.next;    }}

转载地址：http://bhlrb.baihongyu.com/

你可能感兴趣的文章