問題鏈接

19. 刪除鏈表的倒數(shù)第 N 個結(jié)點

問題描述

給你一個鏈表，刪除鏈表的倒數(shù)第 n 個結(jié)點，并且返回鏈表的頭結(jié)點。

示例

解題思路

0.理解

在不考慮釋放被刪除節(jié)點對應的空間的情況下，我們只需要將倒數(shù)第n個節(jié)點的前節(jié)點指向倒數(shù)第n個節(jié)點的后節(jié)點即可。

1.借助數(shù)組

這可能算取巧，遍歷一遍鏈表，將鏈表中的每一個節(jié)點存入list，這時候你想怎么操作就怎么操作了......

2.雙指針

新建一個表頭，將兩個指針放在表頭往后遍歷：
一個指針先跑，使得兩個指針之間隔著n-1個節(jié)點；
當跑得快的指針跑到了最后一個節(jié)點時，另外一個指針跑到了倒數(shù)n+1個節(jié)點；
此時，讓倒數(shù)n+1個節(jié)點的next指向next.next即可。

代碼示例（JAVA）

1.借助數(shù)組

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<ListNode> nodeList = new ArrayList<>();
        ListNode node = head;
        while (node != null) {
            nodeList.add(node);
            node = node.next;
        }

        if (nodeList.size() == n) {
            return head.next;
        }
        nodeList.get(nodeList.size() - n - 1).next = n != 1 ? nodeList.get(nodeList.size() - n + 1) : null;
        return head;
    }
}

執(zhí)行結(jié)果

2.雙指針

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newHead = new ListNode(0, head);
        ListNode first = head;
        ListNode second = newHead;

        for (int i = 0; i < n - 1; i++) {
            first = first.next;
        }
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }

        second.next = second.next.next;
        return newHead.next;
    }
}

執(zhí)行結(jié)果