Leetcode链表-19

虽然很久以前就说要开始刷力扣，也早就注册了账号，但直到暑假才正式开始刷。最开始写每日一题，写了两天发现自己的算法基础还是太薄弱了，被双指针和DP橄榄（×），于是找了一个力扣题目分类汇总的网站：代码随想录，开始简单的跟着刷一刷。大概会隔一段时间出一次博客谈谈遇到的好玩的题？所以是不定期更新吧。

那今天就从链表开始吧（感觉数组还可以？不如链表好玩）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

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

题目链接

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

思路

最容易想到的思路就是，两次遍历，第一次记录链表长度 length，第二次遍历到 length - n处，删除该处后的节点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    int length;
    ListNode cur = head;
    for (length = 0; cur != null; length++) {
        cur = cur.next;
    }
    length = length - n;
    cur = head;
    if (length == 0) {
        return cur.next;
    } 
    else {
        for (int i = 1; i < length; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return head;
    }
}

但是这道题的题目中提到：

进阶：你能尝试使用一趟扫描实现吗？

这时候就需要用到双指针了。

思路：快慢指针均赋值为head，快指针先走n步，随后快慢指针一起走。快指针走到尾节点时，慢指针的下一个节点即为要删除的节点。

注意：若n = length，快指针走过n步后到达null处，此时则要删除第一个节点，可直接返回head->next。

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null)
        return null;
    ListNode cur = head, prev = head;
    //快指针先走n步
    for(int i = 0; i < n; i ++){
        cur = cur.next;
    }
    while (cur.next != null){
        cur = cur.next;
        prev = prev.next;
    }
    if (prev.next == null)
        return null;
    else
        prev.next = prev.next.next;
    return head;
}