題目
??**分別實(shí)現(xiàn)兩個函數(shù)，一個可以刪除單鏈表中倒數(shù)第 K 個節(jié)點(diǎn)，另一個可以刪除雙鏈表中倒數(shù)第 K 個節(jié)點(diǎn)
要求
??如果鏈表長度為 N，時間復(fù)雜度達(dá)到O(N)，額外空間復(fù)雜度達(dá)到O(1)。
思路
??本題較為簡單，實(shí)現(xiàn)方式也是多種多樣的，小編提供一種方法供讀者參考。
??先來看看單鏈表如何調(diào)整。如果鏈表為空或者 K 小于1。這種情況下，參數(shù)是無效的直接返回即可，除此之外，讓鏈表從頭開始走到尾，每移動一步，就讓K的值減1。
??鏈表: 1 → 2 → 3，K = 4，鏈表根本不存在倒數(shù)第4個節(jié)點(diǎn)
??走到的節(jié)點(diǎn): 1 → 2 → 3
??K 變化為: 3 2 1
??鏈表: 1 → 2 → 3，K ＝ 3，鏈表倒數(shù)第3個節(jié)點(diǎn)是1節(jié)點(diǎn)
??走到的節(jié)點(diǎn): 1 → 2 → 3
??K 變化為: 2 1 0
??鏈表: 1 → 2 → 3，K ＝ 2，鏈表倒數(shù)第2個節(jié)點(diǎn)是2節(jié)點(diǎn)
??鏈表:走到的節(jié)點(diǎn): 1 → 2 → 3
??K 變化為:1 → 0 → 1
??由以上三種情況可知，讓鏈表從頭開始走到尾，沒移動一步，就讓 K 值減1，當(dāng)鏈表走到結(jié)尾時，如果值大于0。說明不用調(diào)整鏈表，因?yàn)殒湵砀緵]有倒數(shù)第 K 個節(jié)點(diǎn)，此時將原鏈表直接返回即可；如果 K 值等于0，說明鏈表倒數(shù)第 K 個節(jié)點(diǎn)就是頭節(jié)點(diǎn)，此時直接返回head.next，也就是原鏈表的第二個節(jié)點(diǎn)，讓第二個節(jié)點(diǎn)作為鏈表的頭節(jié)點(diǎn)返回即可，相當(dāng)于刪除頭節(jié)點(diǎn)；接下來，說明一下如果 K 值小于0，該如何處理。
??先明確一點(diǎn)，如果要刪除鏈表的頭節(jié)點(diǎn)之后的某個節(jié)點(diǎn)，實(shí)際上需要找到要刪除節(jié)點(diǎn)的前個節(jié)點(diǎn)，比如: 1 → 2 → 3，如果想除節(jié)點(diǎn)2，則需要找到節(jié)點(diǎn)1，然后把節(jié)點(diǎn)1連到節(jié)點(diǎn)3上(1 → 3)，以此來達(dá)到刪除節(jié)點(diǎn)2的目的。
??如果 K 值小于0，如何找到要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)呢?方法如下:
??1.重新從頭節(jié)點(diǎn)開始走，每移動一步，就讓K的值加1。
??2.當(dāng)K等于0時，移動停止，移動到的節(jié)點(diǎn)就是要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)。
??這樣做是非常好理解的，因?yàn)槿绻湵黹L度為N，要刪除倒數(shù)第K個節(jié)點(diǎn)，很明顯，倒數(shù)第 K 個節(jié)點(diǎn)的前一個節(jié)點(diǎn)就是第 N - K 個節(jié)點(diǎn)。在第一次遍歷后，K 的值變?yōu)?K - N。第二次遍歷時 K 的值不斷加1，加到 0 就停止遍歷，第二次遍歷當(dāng)然會停到第 N - K個節(jié)點(diǎn)的位置。
代碼演示
package com.itz.zcy.listQuestion;
/**
* 分別實(shí)現(xiàn)兩個函數(shù)，一個可以刪除單鏈表中倒數(shù)第 K 個節(jié)點(diǎn)，另一個可以刪除雙鏈表中倒數(shù)第 K 個節(jié)點(diǎn)
* 如果鏈表長度為 N，時間復(fù)雜度達(dá)到O(N)，額外空間復(fù)雜度達(dá)到O(1)。
*/
public class DeleteListKNode {
/**
* 定義節(jié)點(diǎn)
*/
public static class Node {
public int value;
public Node next;
//該變量用來做雙鏈表的指向前區(qū)節(jié)點(diǎn)，在單鏈表的時候請讀者忽略該節(jié)點(diǎn)
public Node last;
public Node(int data) {
this.value = data;
}
}
/**
* 刪除單鏈表的倒數(shù)第k個節(jié)點(diǎn)
* @param head
* @param lastKth
* @return
*/
public static Node removeLastKthNode(Node head, int lastKth) {
// 異常判定
if (head == null || lastKth < 1) {
return head;
}
// 輔助節(jié)點(diǎn)
Node cur = head;
// 遍歷一遍節(jié)點(diǎn)判斷節(jié)點(diǎn)在鏈表的哪兒
while (cur != null) {
lastKth--;
cur = cur.next;
}
// 如果是刪除頭節(jié)點(diǎn)的情況
if (lastKth == 0){
head = head.next;
}
// 找到要刪除的節(jié)點(diǎn)
if (lastKth < 0) {
cur = head;
while (++lastKth != 0) {
cur = cur.next;
}
// 刪除節(jié)點(diǎn)
cur.next = cur.next.next;
}
return head;
}
/**
* 刪除雙鏈表的倒數(shù)第k個節(jié)點(diǎn)
* @param head
* @param lastKth
* @return
*/
public static Node removeLastKthDoubleNode(Node head,int lastKth){
if (head==null||lastKth<1){
return head;
}
Node cur = head;
while (cur !=null){
lastKth--;
cur = cur.next;
}
if (lastKth == 0){
head = head.next;
head.last = null;
}
if (lastKth<0){
cur = head;
while (++lastKth!=0){
cur = cur.next;
}
// 刪除節(jié)點(diǎn) 刪除雙鏈表的某個節(jié)點(diǎn)
Node newNext = cur.next.next;
cur.next = newNext;
if (newNext != null){
newNext.last = cur;
}
}
return head;
}
public static void main(String[] args) {
Node node = new Node(2);
node.next = new Node(4);
node.next.next = new Node(6);
node.next.next.next = new Node(8);
node.next.next.next.next = new Node(3);
node.next.next.next.next.next = new Node(5);
node.next.next.next.next.next.next = new Node(7);
Node head = removeLastKthNode(node, 5);
while (true){
if (head!=null){
if (head.next == null){
System.out.print(head.value);
}else {
System.out.print(head.value+" → ");
}
}else {
break;
}
head = head.next;
}
System.out.println();
Node node2 = new Node(2);
node2.next = new Node(4);
node2.next.last= node2;
node2.next.next = new Node(6);
node2.next.next.last = node2.next;
node2.next.next.next = new Node(8);
node2.next.next.next.last = node2.next.next;
node2.next.next.next.next = new Node(3);
node2.next.next.next.next.last = node2.next.next.next;
node2.next.next.next.next.next = new Node(5);
node2.next.next.next.next.next.last = node2.next.next.next.next;
node2.next.next.next.next.next.next = new Node(7);
node2.next.next.next.next.next.next.last = node2.next.next.next.next.next;
Node head2 = removeLastKthDoubleNode(node2, 5);
while (true){
if (head2!=null){
if (head2.next == null){
System.out.print(head2.value);
}else {
System.out.print(head2.value+" ? ");
}
}else {
break;
}
head2 = head2.next;
}
}
// 2 → 4 → 8 → 3 → 5 → 7
// 2 ? 4 ? 8 ? 3 ? 5 ? 7
}
總結(jié)
該題目比較簡單，方法多種多樣；時間復(fù)雜度是O(n),空間復(fù)雜度O(1)。
文獻(xiàn)：左程云著 《程序員代碼面試指南IT名企算法與數(shù)據(jù)結(jié)構(gòu)題目最優(yōu)解》（第二版）
版權(quán)聲明：此文版權(quán)歸作者所有！
