Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4, and you are given the third node with value3, the linked list should become 1 -> 2 -> 4 after calling your function.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution
{
public void deleteNode(ListNode node)
{
}
}
Solution:
咋一看這道題感覺就是最基本的鏈表操作，剛準(zhǔn)備動手發(fā)現(xiàn)并不能訪問鏈表本身（并沒有給出鏈表的頭結(jié)點(diǎn)）泌辫，又由于單鏈表沒有前向指針，所以不能用簡單的刪除節(jié)點(diǎn)的思路松忍。
參考Discuss后得到思路：
- 判斷待刪除的node是否是最后一個node，如果是則直接將最后一個節(jié)點(diǎn)刪除（雖然該該題目指明不需要考慮鏈表中的最后一個節(jié)點(diǎn)筷厘，但考慮有最后一個節(jié)點(diǎn)的情況更為周全）鸣峭。Java似乎無法實(shí)現(xiàn)刪除最后一個節(jié)點(diǎn)宏所，無法將所有指向最后一個節(jié)點(diǎn)的引用置為null（一共有兩個引用指向最后一個節(jié)點(diǎn)，分別是該函數(shù)的參數(shù)node摊溶，和最后一個節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的next）爬骤。如果用C/C++則可以直接調(diào)用delete運(yùn)算符。
- （如果不是最后一個節(jié)點(diǎn)）將后一個節(jié)點(diǎn)的val拷貝到當(dāng)前節(jié)點(diǎn)val莫换，然后刪除后一個節(jié)點(diǎn)（將當(dāng)前節(jié)點(diǎn)的next指向null）
code：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution
{
public void deleteNode(ListNode node)
{
if(node.next == null) // this part is useless according to the requirement and Java
node = null; // in C++ we can delete node;
else
{
node.val = node.next.val;
node.next = node.next.next;
}
}
}
