LeetCode第[19]题(Java)：Remove Nth Node From End of List（删除链表的倒数第N个节点）

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

难度：Medium

题目内容：

Given a linked list, remove the n-th node from the end of list and return its head.

翻译：给定一个链表，删除倒数第n个节点并返回其头部。

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

给出的n一定是有效的。

我的思路：数据结构——因为要倒着数，所以考虑用栈；　

　　　　　算法——用while循环将链表节点按顺序全部存入栈中，然后再对n进行while循环自减，直到n==1，退出循环，此时栈顶就是要删除的节点，用一个节点del存储它，再弹出一个就是它的前驱节点pre。pre.next = del.next;这就是删除节点。

我的代码：

    public ListNode removeNthFromEnd(ListNode head, int n) {

        if (head==null || n < 1) {

            return null;

        }

        Stack<ListNode> st = new Stack<ListNode>();

        ListNode cur = head;

        while (cur != null) {

            st.push(cur);

            cur = cur.next;

        }

        while (n-- != 1) {

            st.pop();

        }

        ListNode del = st.pop();

        if (st.size() == 0) { // 此时栈如果空了，那么删除的就是最开始的头结点，这时候直接返回del.next 即可。

            return del.next;

        }

        ListNode pre = st.pop();

        pre.next = del.next;

        del = null;

        return head;

    }

我的复杂度：O（N + n） N为总长度，n为倒数个数

编码过程中的问题：

1、一开始没考虑到要删的del没有前驱的情况，得到del时，栈就空了，再pop()就报错了:EmptyStackException 错误用例：[1],1。

参考答案代码：

     public ListNode removeNthFromEnd(ListNode head, int n) {

         ListNode newHead = new ListNode(0);  // 因为可能要删除的就是head所以起一个头结点 0

         newHead.next = head;

         ListNode pre = newHead;  // 慢指针

         ListNode fast = newHead;  // 快指针

         while(n-- > 0){

             fast = fast.next;  // 初始，快指针与慢指针相差n

         }

         while(fast.next!=null){

             fast = fast.next;

             pre=pre.next;

         }

         pre.next = pre.next.next;

         return newHead.next;

      }

参考答案复杂度：O（N + n）不过它的空间复杂度是O(1) ，我写的那个空间复杂度O（N）

答案思路：利用快慢指针（其实叫前后指针更贴切）的概念，初始时快慢指针之间的距离为n，然后同速前进，当快指针的next==null的时候（注意不是快指针自己），此时慢指针的next必然指向倒数第n个。【因为可能要删除的就是head所以起一个头结点 0 】

此处就不需要del的判断了，所以直接 pre.next = pre.next.next; 。（ps：其实我都忘了还可以这么删除，啊哈哈哈）

巴特西

LeetCode第[19]题(Java)：Remove Nth Node From End of List（删除链表的倒数第N个节点）

最新文章

热门文章