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

ゝ一世哀愁。 2022-12-15 14:29 102阅读 0赞

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

## 计算链表长度 ##

先求出长度，再找到要删除的那个节点的前一个节点。  
![在这里插入图片描述][20201018095432817.png]

curr.next = curr.next.next;

代码

/** * 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) { 
            int length = 0;
            ListNode curr = head;
            while(curr!=null){ 
                length++;
                curr = curr.next;
            }
            //链表 1->2->3->4->5
            //需要删除倒数第2个，就是删除顺数第4个，需要找到顺数第3个，5-2=3,
            //需要删除倒数第1个，就是删除顺数第5个，需要找到顺数第4个，5-1=4，
            //需要删除倒数第2个，就是删除顺数第4个，需要找到顺数第3个，5-2=3，
            //需要删除倒数第5个，就是删除顺数第1个，需要找到顺数第0个，5-5=0。
            int index = length - n;
            if(index==0) { 
            	return head.next;
            }
            curr = head;
            for(int i=1;i<index;i++){ 
                curr = curr.next;
            }
            curr.next = curr.next.next;
            return head;
        }
    }

## 快慢指针 ##

![在这里插入图片描述][20201018102836133.gif_pic_center]  
比如删除倒数第2个，算法如下，快指针先走2步，然后快慢指针一起走，直到快指针返回NULL，此时，慢指针指向待删除节点的前一个节点。  
**图片来源 公众号：五分钟学算法**  
以下代码为c语言写的。

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
    struct ListNode* removeNthFromEnd(struct ListNode* head, int n){ 
        struct ListNode* dummy = malloc(sizeof(struct ListNode));
        dummy->val = 0, dummy->next = head;
        struct ListNode* first = head;
        struct ListNode* second = dummy;
        for (int i = 0; i < n; ++i) { 
            first = first->next;
        }
        while (first) { 
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        struct ListNode* ans = dummy->next;
        free(dummy);
        return ans;
    }

[20201018095432817.png]: /images/20221123/253b928c16af43989f51ee249da4a319.png
[20201018102836133.gif_pic_center]: /images/20221123/bc2a251dc9b546cba286f3321222368e.png