牛客網程式設計高頻題19——NC53删除連結清單的倒數第n個節點

目錄

删除連結清單的倒數第n個節點

描述

備注：

示例1

輸入：

傳回值：

方法一：暴力搜尋

方法二：快慢指針

删除連結清單的倒數第n個節點

描述

給定一個連結清單，删除連結清單的倒數第 n 個節點并傳回連結清單的頭指針，例如，

給出的連結清單為：1→2→3→4→5，n=2

删除了連結清單的倒數第 n 個節點之後，連結清單變為1→2→3→5.

備注：

題目保證 n 一定是有效的，請給出請給出時間複雜度為

的算法

連結清單資料結構為：

public class ListNode {
    int val;
    ListNode next = null;
}
           

示例1

輸入：

{1,2},2
           

傳回值：

{2}
           

方法一：暴力搜尋

暴力破解，直接周遊到最後一個節點，統計連結清單的長度為L，然後再次重頭周遊删除第L+1-n個節點

import java.util.*;

public class Solution {
    /**
     * 
     * @param head ListNode類 
     * @param n int整型 
     * @return ListNode類
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if(head.next==null) return null;
        
        int len=0;
        ListNode cur=head;
        while(cur!=null){
            cur=cur.next;
            len++;
        }

        if(len==n) return head.next;
        cur=new ListNode(0);
        cur.next=head;

        int i=0;
        while(i<len-n){
            cur=cur.next;
            i++;
        }
        cur.next=cur.next.next;
        return head;
    }
}
           

這種方法比較笨，時間複雜度較大，

方法二：快慢指針

思路是先定義兩個指針都指向head，然後快指針先走n步，接着兩個指針同時移動，快指針走到末尾時慢指針指向的節點就是要删除的節點

import java.util.*;
public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if(head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        for(int i=0;i<n;i++){
            fast=fast.next;
        }
        if(fast==null){
            return head.next;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return head;
    }
}