LeetCode日记–19.remove the Nth Node from the end of List

发布于 2020-09-19  120 次阅读


题目如下:

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

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:

Given n will always be valid.

Follow up:

Could you do this in one pass?

本人思路:

用数学推导可以知道就是删除第L - (n - 1)个节点。先遍历一遍得到L的值,再从头遍历至第L - n个节点,将其的next指向L-n+2节点就可以。但是这里要注意一些奇怪的case,比如:只有一个节点,要删除的节点在链表头部等情况。

本人代码(又臭又长)如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p =head;
        int count=0;
        // 遍历得到链表长度
        while(p!=null){
            count++;
            p = p.next;
        }
        p = head;
        int location = count - ( n - 1 );
        if(location==1||count==1){
            head = head.next;
            return head;
        }
        if(location==2){
            ListNode temp = p.next;
            p.next = temp.next;
            temp.next=null;
            return head;
        }
        for(int i=1;i<=location-2;i++)
            p=p.next;
        ListNode temp = p.next;
        p.next = temp.next;
        temp.next=null;
        return head;
    }
}

该方法的官方代码如下:

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int length  = 0;
    ListNode first = head;
    while (first != null) {
        length++;
        first = first.next;
    }
    length -= n;
    first = dummy;
    while (length > 0) {
        length--;
        first = first.next;
    }
    first.next = first.next.next;
    return dummy.next;
}

作者:LeetCode
链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-by-l/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

一些感悟:

可以看到我的代码又臭又长的主要原因就是一开始设计的时候没有考虑到从头删除或者 链表只有一个内容这种特殊情况。官方代码设置了一个头指针,指向头结点,在遍历删除时从头指针开始,就可以防止需要删除头结点这样的情况了。

改进后我的代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p =head;
        ListNode dummmy = new ListNode(0);
        dummmy.next = head;
        int count=0;
        // 遍历得到链表长度
        while(p!=null){
            count++;
            p = p.next;
        }
        p = dummmy;
        int location = count - ( n - 1 );
        for(int i=1;i<=location-1;i++)
            p=p.next;
        ListNode temp = p.next;
        p.next = temp.next;
        temp.next=null;
        return dummmy.next;
    }
}

最优解:

但是题目要求的是“do this in one pass”诶!

那么让我们来冷静分析一下之前要遍历两遍的原因:因为我们一开始并不知道链表的长度,因此要先遍历一遍知道长度以后,才方便去删除倒数第n个。

这时候又是双指针出场了,我们先用一个指针往后移动n位,另一个指针还保持在链表起始处,这是他们俩的距离就是n,那么当右指针到达链表末尾时,左指针自然就是指向倒数第n个了。

示意图

代码如下:

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

作者:LeetCode
链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-by-l/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

感悟:

双指针你呀,总能给我整出些新花样!.jpg


你好哇!欢迎来到雷公马碎碎念的地方:)