前言

分享一下 騰訊常考的十道算法題（真題）。在金三銀四，希望對大家有幫助呀。

重排鏈表

最長遞增子序列

環(huán)形鏈表

反轉(zhuǎn)鏈表

最長回文子串

全排列

LRU 緩存

合并K個升序鏈表

無重復(fù)字符的最長子串

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

1. 重排鏈表

給定一個單鏈表 L 的頭節(jié)點 head ，單鏈表 L 表示為：

L0 → L1 → … → Ln - 1 → Ln

請將其重新排列后變?yōu)?#xff1a;

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

輸入：

head = [1,2,3,4]

輸出：

[1,4,2,3]

思路：

如果是數(shù)組就好了，哈哈，因為數(shù)組可以直接通過下標(biāo)訪問，很容易就可以解答這道題了。但是這是鏈表。**鏈表不支持下標(biāo)訪問，**我們沒辦法隨機(jī)訪問到鏈表任意位置的元素，怎么辦呢？

我們可以先遍歷一下，用數(shù)組把鏈表的元素按順序存儲起來呀，然后就可以把它當(dāng)做數(shù)組這么訪問來用了對吧，最后重建下鏈表即可啦。

ArrayList的底層就是數(shù)組，我們先用它存儲鏈表就好，如下：

List<ListNode> list = new ArrayList<ListNode>();ListNode node = head;while (node != null) {list.add(node);node = node.next; }

有了一個數(shù)組結(jié)構(gòu)的鏈表后，如何重建鏈表呢？回頭多看示例兩眼，很容易就發(fā)小規(guī)律啦：先排第1個，再排倒數(shù)第1個，接著排第2個，緊接著倒數(shù)第2個。顯然這個規(guī)律很明顯，代碼也比較好實現(xiàn)：

int i = 0; int j = list.size()-1; while(i<j){list.get(i).next = list.get(j);i++;if(i==j){break;}list.get(j).next = list.get(i);j--; } //大家畫個圖就很清晰知道為什么需要這行了，哈哈list.get(i).next = null;

完整實現(xiàn)代碼如下：

class Solution {public void reorderList(ListNode head) {if (head == null) {return;}List<ListNode> list = new ArrayList<ListNode>();ListNode node = head;while (node != null) {list.add(node);node = node.next;}int i = 0, j = list.size() - 1;while (i < j) {list.get(i).next = list.get(j);i++;if (i == j) {break;}list.get(j).next = list.get(i);j--;}list.get(i).next = null;} }

2. 最長遞增子序列

給你一個整數(shù)數(shù)組 nums ，找到其中最長嚴(yán)格遞增子序列的長度。

實例1：

輸入：nums = [10,9,2,5,3,7,101,18] 輸出：4 解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。

實例2：

輸入：nums = [0,1,0,3,2,3] 輸出：4

思路：

這道題是求最值問題，可以使用動態(tài)規(guī)劃解決。動態(tài)規(guī)劃的解題整體思路就是：

窮舉分析

分析找規(guī)律，拆分子問題

確定邊界

確定最優(yōu)子結(jié)構(gòu)

寫出狀態(tài)轉(zhuǎn)移方程

2.1 窮舉分析

動態(tài)規(guī)劃的核心思想包括拆分子問題，記住過往，減少重復(fù)計算。所以我們在思考原問題：數(shù)組num[i]的最長遞增子序列長度時，可以思考下相關(guān)子問題，比如原問題是否跟子問題num[i-1]的最長遞增子序列長度有關(guān)呢？

自底向上的窮舉過程：

• 當(dāng)nums只有一個元素10時，最長遞增子序列是[10],長度是1.

• 當(dāng)nums需要加入一個元素9時，最長遞增子序列是[10]或者[9],長度是1。

• 當(dāng)nums再加入一個元素2時，最長遞增子序列是[10]或者[9]或者[2],長度是1。

• 當(dāng)nums再加入一個元素5時，最長遞增子序列是[2,5],長度是2。

• 當(dāng)nums再加入一個元素3時，最長遞增子序列是[2,5]或者[2,3],長度是2。

• 當(dāng)nums再加入一個元素7時，,最長遞增子序列是[2,5,7]或者[2,3,7],長度是3。

• 當(dāng)nums再加入一個元素101時，最長遞增子序列是[2,5,7,101]或者[2,3,7,101],長度是4。

• 當(dāng)nums再加入一個元素18時，最長遞增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],長度是4。

• 當(dāng)nums再加入一個元素7時,最長遞增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],長度是4.

2.2 分析找規(guī)律，拆分子問題

通過上面分析，我們可以發(fā)現(xiàn)一個規(guī)律：

如果新加入一個元素nums[i], 最長遞增子序列要么是以nums[i]結(jié)尾的遞增子序列，要么就是nums[i-1]的最長遞增子序列。看到這個，是不是很開心，nums[i]的最長遞增子序列已經(jīng)跟子問題 nums[i-1]的最長遞增子序列有關(guān)聯(lián)了。

原問題數(shù)組nums[i]的最長遞增子序列 = 子問題數(shù)組nums[i-1]的最長遞增子序列/nums[i]結(jié)尾的最長遞增子序列

是不是感覺成功了一半呢？但是如何把nums[i]結(jié)尾的遞增子序列也轉(zhuǎn)化為對應(yīng)的子問題呢？要是nums[i]結(jié)尾的遞增子序列也跟nums[i-1]的最長遞增子序列有關(guān)就好了。又或者nums[i]結(jié)尾的最長遞增子序列，跟前面子問題num[j]（0=<j<i）結(jié)尾的最長遞增子序列有關(guān)就好了，帶著這個想法，我們又回頭看看窮舉的過程：

nums[i]的最長遞增子序列，不就是從以數(shù)組num[i]每個元素結(jié)尾的最長子序列集合，取元素最多（也就是長度最長）那個嘛，所以原問題，我們轉(zhuǎn)化成求出以數(shù)組nums每個元素結(jié)尾的最長子序列集合，再取最大值嘛。哈哈，想到這，我們就可以用dp[i]表示以num[i]這個數(shù)結(jié)尾的最長遞增子序列的長度啦，然后再來看看其中的規(guī)律：

其實，nums[i]結(jié)尾的自增子序列，只要找到比nums[i]小的子序列，加上nums[i] 就可以啦。顯然，可能形成多種新的子序列，我們選最長那個，就是dp[i]的值啦

• nums[3]=5,以5結(jié)尾的最長子序列就是[2,5],因為從數(shù)組下標(biāo)0到3遍歷，只找到了子序列[2]比5小，所以就是[2]+[5]啦，即dp[4]=2

• nums[4]=3,以3結(jié)尾的最長子序列就是[2,3],因為從數(shù)組下標(biāo)0到4遍歷，只找到了子序列[2]比3小，所以就是[2]+[3]啦，即dp[4]=2

• nums[5]=7，以7結(jié)尾的最長子序列就是[2,5,7]和[2,3,7],因為從數(shù)組下標(biāo)0到5遍歷，找到2,5和3都比7小，所以就有[2,7],[5,7],[3,7],[2,5,7]和[2,3,7]這些子序列，最長子序列就是[2,5,7]和[2,3,7]，它倆不就是以5結(jié)尾和3結(jié)尾的最長遞增子序列+[7]來的嘛！所以，dp[5]=3 =dp[3]+1=dp[4]+1。

很顯然有這個規(guī)律：一個以nums[i]結(jié)尾的數(shù)組nums

• 如果存在j屬于區(qū)間[0，i-1],并且num[i]>num[j]的話，則有:dp(i) =max(dp(j))+1。

2.3 確定邊界

當(dāng)nums數(shù)組只有一個元素時，最長遞增子序列的長度dp(1)=1,當(dāng)nums數(shù)組有兩個元素時，dp(2) =2或者1， 因此邊界就是dp(1)=1。

2.4 確定最優(yōu)子結(jié)構(gòu)

從2.2 窮舉分析找規(guī)律，我們可以得出，以下的最優(yōu)結(jié)構(gòu)：

dp(i) =max(dp(j))+1，存在j屬于區(qū)間[0，i-1],并且num[i]>num[j]。

max(dp(j)) 就是最優(yōu)子結(jié)構(gòu)。

2.5 寫出狀態(tài)轉(zhuǎn)移方程

通過前面分析，我們就可以得出狀態(tài)轉(zhuǎn)移方程啦：

所以數(shù)組nums[i]的最長遞增子序列就是：

最長遞增子序列 =max(dp[i])

完整代碼實現(xiàn)如下：

class Solution {public int lengthOfLIS(int[] nums) {if (nums.length == 0) {return 0;}int[] dp = new int[nums.length];//初始化就是邊界情況dp[0] = 1;int maxans = 1;//自底向上遍歷for (int i = 1; i < nums.length; i++) {dp[i] = 1;//從下標(biāo)0到i遍歷for (int j = 0; j < i; j++) {//找到前面比nums[i]小的數(shù)nums[j],即有dp[i]= dp[j]+1if (nums[j] < nums[i]) {//因為會有多個小于nums[i]的數(shù)，也就是會存在多種組合了嘛，我們就取最大放到dp[i]dp[i] = Math.max(dp[i], dp[j] + 1);}}//求出dp[i]后，dp最大那個就是nums的最長遞增子序列啦maxans = Math.max(maxans, dp[i]);}return maxans;} }

3. 環(huán)形鏈表

給定一個鏈表的頭節(jié)點head ，返回鏈表開始入環(huán)的第一個節(jié)點。如果鏈表無環(huán)，則返回 null。

實例：

輸入：head = [3,2,0,-4], pos = 1 輸出：返回索引為 1 的鏈表節(jié)點 解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

如果判斷鏈表是否有環(huán)，我們可以使用快慢指針，快指針是慢指針?biāo)俣鹊膬杀?#xff0c;當(dāng)兩個指針相遇時，即表示有環(huán)。

boolean hasCycle(ListNode head ){ListNode slow = head;ListNode fast = head;while(fast!=null && fast.next!=null){fast = fast.next.next;slow = slow.next;if(fast==slow){return true;}}return false; }

我們可以很容易就判斷有環(huán)，但是如何返回入環(huán)的第一個節(jié)點呢？我們來畫個圖分析一波：

假設(shè)起點為A，入環(huán)點為B，快慢指針相遇點為C，慢指針走到相遇點為k步，B到C的距離為m。設(shè)環(huán)型周長為X。因為快指針?biāo)俣仁锹羔樀?strong>2倍。則有：

K-m + X + m = 2K = 快指針走的舉例

所以周長X = K。相遇后，快指針到繼續(xù)往前走，走到入環(huán)點B，剛好距離是X-m = K-m。而起點到B節(jié)點，距離也是K-m。因此，快慢指針相遇后，慢指針回到起點，這時候快慢指針一樣的速度走，相遇時，就是入環(huán)點啦，是不是無巧不成書呀，哈哈哈。

完整代碼如下：

public class Solution {public ListNode detectCycle(ListNode head) {if(head ==null){return null;}ListNode fast = head;ListNode slow = head;while(fast!=null&&fast.next!=null){fast = fast.next.next;slow = slow.next;//快慢指針相等表示有環(huán)if(slow==fast){//回到起點一起相同速度走while(head!=fast){head = head.next;fast = fast.next;}return head;}}return null;} }

4. 反轉(zhuǎn)鏈表

給你單鏈表的頭節(jié)點 head ，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

輸入：head = [1,2,3,4,5] 輸出：[5,4,3,2,1]

完整代碼如下：

class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode next = head;ListNode curr = head ;while(curr!=null){next = curr.next ;curr. next = prev;prev = curr ;curr = next ;}return prev;} }

之前圖解過這道題，大家可以看下哈：

看一遍就理解，圖解單鏈表反轉(zhuǎn)

5. 最長回文子串

給你一個字符串 s，找到 s 中最長的回文子串。

實例1：

輸入：s = "babad" 輸出："bab" 解釋："aba" 同樣是符合題意的答案。

這道題可以使用中心擴(kuò)展法實現(xiàn)，從中間開始向兩邊擴(kuò)散來判斷回文串。

for 0 <= i < len(s):找到以 s[i] 為中心的回文串更新答案

但是回文串可能是長度可能是奇數(shù)，也可能是偶數(shù)，因此需要加多一步：

for 0 <= i < len(s):找到以 s[i] 為中心的回文串找到以 s[i] 和s[i+1] 為中心的回文串更新答案

完整代碼如下：

class Solution {public String longestPalindrome(String s) {if(s==null|| s.length()<2){return s;}String result ="";for(int i=0;i<s.length();i++){String r1 = subLongestPalindrome(s,i,i);String r2 = subLongestPalindrome(s,i,i+1);String tempMax= r1.length()>r2.length()? r1 :r2;result = tempMax.length()> result.length()?tempMax:result;}return result;}private String subLongestPalindrome(String s,int l,int r){while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){l--;r++;}return s.substring(l+1,r);} }

6.全排列

給定一個不含重復(fù)數(shù)字的數(shù)組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

示例 1：

輸入：nums = [1,2,3] 輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

輸入：nums = [0,1] 輸出：[[0,1],[1,0]]

這道題可以用回溯算法解決，完整代碼如下：

class Solution {//全排列，即所有路徑集合List<List<Integer>> allPath = new LinkedList<>();public List<List<Integer>> permute(int[] nums) {//當(dāng)前路徑，入口路徑，path是空的List<Integer> path = new LinkedList<>();//遞歸函數(shù)入口，可做選擇是nums數(shù)組backTrace(nums,path);return allPath;}public void backTrace(int[] nums,List<Integer> path){//已走路徑path的數(shù)組長度等于nums的長度,表示走到葉子節(jié)點，所以加到全排列集合if(nums.length==path.size()){allPath.add(new LinkedList(path));return;}for(int i=0;i<nums.length;i++){//剪枝，排查已經(jīng)走過的路徑if(path.contains(nums[i])){continue;}//做選擇，加到當(dāng)前路徑path.add(nums[i]);//遞歸，進(jìn)入下一層的決策backTrace(nums,path);//取消選擇path.remove(path.size() - 1);}} }

大家可以看下這篇回溯文章哈，有回溯算法的框架套用。

面試必備：回溯算法詳解

7. LRU 緩存

請你設(shè)計并實現(xiàn)一個滿足 LRU (最近最少使用) 緩存 約束的數(shù)據(jù)結(jié)構(gòu)。

實現(xiàn) LRUCache 類：

• LRUCache(int capacity) 以 正整數(shù) 作為容量 capacity 初始化 LRU 緩存

• int get(int key) 如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，否則返回 -1 。

• void put(int key, int value) 如果關(guān)鍵字 key 已經(jīng)存在，則變更其數(shù)據(jù)值 value ；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導(dǎo)致關(guān)鍵字?jǐn)?shù)量超過 capacity ，則應(yīng)該 逐出 最久未使用的關(guān)鍵字。

函數(shù) get 和 put 必須以O(shè)(1) 的平均時間復(fù)雜度運行。

示例：

輸入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 輸出 [null, null, null, 1, null, -1, null, -1, 3, 4]解釋 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 緩存是 {1=1} lRUCache.put(2, 2); // 緩存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 該操作會使得關(guān)鍵字 2 作廢，緩存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 該操作會使得關(guān)鍵字 1 作廢，緩存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4

這道題，出現(xiàn)的頻率還是挺高的，很多小伙伴在面試時，都反饋自己遇到過原題。

LRU，Least Recently Used，即最近使用過的數(shù)據(jù)是有用的，可以使用雙鏈表+Hashmap解答，雙鏈表用于存儲LRUCache的數(shù)據(jù)，Hashmap實現(xiàn)O（1）的平均時間復(fù)雜度。

• 每次從鏈表尾部添加元素，靠尾的元素就是最近使用過

• 某個key可以通過哈希表快速定位到節(jié)點。

對于雙鏈表，需要做哪些事呢。

• 首先是鏈表初始化，為了方便處理i，虛擬一個頭節(jié)點和尾結(jié)點。

• 添加元素時，放到鏈表的尾部，表示該元素最近使用過

• 刪除雙向鏈表的某個節(jié)點

• 刪除并返回頭節(jié)點，表示刪除最久未使用的元素

• 返回鏈表當(dāng)前長度

LRU緩存有哪些方法

• 構(gòu)造函數(shù)初始化方法

• get和put方法

• makeRecently 設(shè)置某個元素最近使用過的方法，哈希表已經(jīng)有該元素

• addRecently 添加最近使用過的元素，同時更新map

• deleteKey 刪除某個key對應(yīng)的元素,同時刪除map上的節(jié)點

• removeLeastRecently 刪除最久未使用的元素

完整代碼如下：

class Node {int key,val;Node next,prev;public Node(int key,int val){this.key = key;this.val = val;} }class DoubleList {//虛擬出頭節(jié)點和尾結(jié)點private Node head, tail;private int size;//初始化雙鏈表public DoubleList() {//虛擬頭結(jié)點head = new Node(0, 0);//虛擬頭結(jié)點tail = new Node(0, 0);head.next = tail;tail.prev = head;size = 0;}//要加到鏈表尾部，且越靠近鏈表尾部，越表示最近使用過public void addLast(Node x) {//比如當(dāng)前鏈表為：head <-> 1 <-> tail，加入結(jié)點x = 2x.prev = tail.prev;// 完成結(jié)點2指向兩端的箭頭 head <-> 1 <- 2 -> tail; 此時tail.pre = 結(jié)點1還未斷開x.next = tail;//head <-> 1 <-> 2 -> tail;tail.prev.next = x;//head <-> 1 <-> 2 <-> tail;tail.prev = x;//更新鏈表長度size++;}// 刪除指定結(jié)點public void remove(Node x) {x.prev.next = x.next;x.next.prev = x.prev;size--;}// 刪除并返回頭結(jié)點public Node removeHead() {if (head.next == tail) {return null;}Node first = head.next;// size在remove中更新了remove(first);// 用作在哈希表中移除最久未使用的數(shù)據(jù)值return first;}// 獲取鏈表長度public int getSize() {return size;} }public class LRUCache {private Map<Integer, Node> map;private DoubleList doubleList;private int cap;public LRUCache(int capacity) {this.map = new HashMap<>();this.doubleList = new DoubleList();this.cap = capacity;}public int get(int key) {if (map.containsKey(key)) {// 先將key標(biāo)記為最近使用，再返回valuemakeRecently(key);return map.get(key).val;} else {return -1;}}public void put(int key, int value) {if (map.containsKey(key)) {deleteKey(key); // 從原map中移除該keyaddRecently(key, value); // 更新最近使用return;}int size = doubleList.getSize();if (size == cap) { // 說明需要移除最久未使用的元素了removeLeastRecently();}addRecently(key, value); //添加新的元素進(jìn)來}public void makeRecently(int key) { // 將某個key標(biāo)記為最近使用的元素（map中已存在的）Node x = map.get(key);doubleList.remove(x); // 先從雙鏈表刪除doubleList.addLast(x); // 再添加到鏈表末尾， 因為尾部是最近使用過的元素}public void addRecently(int key, int value) { // 添加最近使用過的元素Node x = new Node(key, value);doubleList.addLast(x);map.put(key, x); //更新map}public void deleteKey(int key) {Node x = map.get(key);map.remove(key);doubleList.remove(x); // 在map中和cache中同時刪除}// 刪除最久未使用的元素public void removeLeastRecently() {// 最久未使用的一定在鏈表頭部Node oldNode = doubleList.removeHead();int oldKey = oldNode.key;map.remove(oldKey);} }

8. 合并K個升序鏈表

給你一個鏈表數(shù)組，每個鏈表都已經(jīng)按升序排列。請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。

示例 1：

輸入：lists = [[1,4,5],[1,3,4],[2,6]] 輸出：[1,1,2,3,4,4,5,6] 解釋：鏈表數(shù)組如下： [1->4->5,1->3->4,2->6 ] 將它們合并到一個有序鏈表中得到。 1->1->2->3->4->4->5->6

合并兩個有序鏈表，是比較簡單的，相信大家都會做。那么如何合并K個有序鏈表呢？其實道理是一樣的，我們可以借用優(yōu)先級隊列找出最小節(jié)點，完整代碼如下：

class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists.length==0){return null;}//虛擬節(jié)點ListNode head = new ListNode(0);ListNode tail = head;//優(yōu)先隊列PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length,(a, b)->(a.val-b.val));//將K個鏈表頭節(jié)點合并最小堆for (ListNode node: lists) {if (node != null) {queue.add(node);}}while (!queue.isEmpty()) {//獲取最小節(jié)點，放到結(jié)果鏈表中ListNode node = queue.poll();tail.next = node;if (node.next != null) {queue.add(node.next);}//指針鏈表一直往前tail = tail.next;}return head.next;} }

9. 無重復(fù)字符的最長子串

給定一個字符串 s ，請你找出其中不含有重復(fù)字符的 最長子串 的長度。

示例 1:

輸入: s = "abcabcbb" 輸出: 3 解釋: 因為無重復(fù)字符的最長子串是 "abc"，所以其長度為 3。

示例 2:

輸入: s = "bbbbb" 輸出: 1 解釋: 因為無重復(fù)字符的最長子串是 "b"，所以其長度為 1。

這道題可以使用滑動窗口來實現(xiàn)。滑動窗口就是維護(hù)一個窗口，不斷滑動，然后更新答案。

滑動窗口的大致邏輯框架，偽代碼如下：

int left =0，right = 0; while (right < s.size()){//增大窗口window.add(s[right]);right++;while (window needs shrink){//縮小窗口window.remove (s[left]);left ++;} }

解法流程如下：

• 首先呢，就是獲取原字符串的長度。

• 接著維護(hù)一個窗口（數(shù)組、哈希、隊列）

• 窗口一步一步向右擴(kuò)展

• 窗口在向右擴(kuò)展滑動過程，需要判斷左邊是否需要縮減

• 最后比較更新答案

完整代碼如下：

int lengthOfLongestSubstring(String s){//獲取原字符串的長度int len = s.length();//維護(hù)一個哈希集合的窗口Set<Character> windows = new HashSet<>();int left=0,right =0;int res =0;while(right<len){char c = s.charAt(right);//窗口右移right++;//判斷是否左邊窗口需要縮減，如果已經(jīng)包含，那就需要縮減while(windows.contains(c)){windows.remove(s.charAt(left));left++;}windows.add(c);//比較更新答案res = Math.max(res,windows.size());}return res; }

之前寫過一篇滑動窗口解析，大家有興趣可以看下哈：

leetcode必備算法：聊聊滑動窗口

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

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

示例 ：

輸入：head = [1,2,3,4,5], n = 2 輸出：[1,2,3,5]

這道題可以使用雙指針解決。既然我們要找到倒數(shù)第n個節(jié)點，我們可以使用兩個指針first 和 second同時對鏈表進(jìn)行遍歷，并且first 比second超前 n個節(jié)點。當(dāng) first遍歷到鏈表的末尾時，second 就恰好處于倒數(shù)第n個節(jié)點。

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);ListNode first = head;ListNode second = dummy;//first 比second先走n個節(jié)點for (int i = 0; i < n; ++i) {first = first.next;}//直到走到鏈表尾部while (first != null) {first = first.next;second = second.next;}//刪除節(jié)點second.next = second.next.next;ListNode ans = dummy.next;return ans;} }

總結(jié)

以上是生活随笔為你收集整理的十道经典面试算法真题详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。