JZ73 翻轉單詞序列
（中等）
題目
描述 牛客最近來了一個新員工Fish，每天早晨總是會拿着一本英文雜志，寫些句子在本子上。同僚Cat對Fish寫的内容頗感興趣，有一天他向Fish借來翻看，但卻讀不懂它的意思。例如，“nowcoder. a am I”。後來才意識到，這家夥原來把句子單詞的順序翻轉了，正确的句子應該是“I am a nowcoder.”。Cat對一一的翻轉這些單詞順序可不在行，你能幫助他麼？
【算法】解題總結：劍指Offer 73 翻轉單詞序列、劍指Offer 18 删除連結清單的節點（2種思路） 示例1
輸入：
“nowcoder. a am I”
傳回值：
“I am a nowcoder.”
示例2
輸入：
“”
傳回值：
“”
思路
隻需先定義一個存儲結果的字元串變量，将傳入的反序的參數字元串按空格分割開後得到一個字元串數組，逆向周遊這個數組，每次添加到之前預先定義的字元串變量的末尾即可，本題用 Java 來做十分得簡單，但是歸為了較難的題型，可能對于C/C++ 的代碼實作者來說，确實有些額外的思考工作，除此之外我想不到還有什麼能讓這道題歸為較難的原因。
實作
public class JZ73翻轉單詞序列 {
public String ReverseSentence(String str) {
if (str == null || str.length() == 0) {
return str;
}
String[] words = str.split(" ");
String[] res = new String[words.length];
String reverse = "";
for (int i = words.length - 1; i >= 0; i--) {
reverse += words[i] + " ";
}
return reverse.substring(0, reverse.length() - 1);
}
} 删除連結清單的節點
（中等）
題目
描述
給定單向連結清單的頭指針和一個要删除的節點的值，定義一個函數删除該節點。傳回删除後的連結清單的頭節點。
1.此題對比原題有改動
2.題目保證連結清單中節點的值互不相同
3.該題隻會輸出傳回的連結清單和結果做對比，是以若使用 C 或 C++ 語言，你不需要 free 或 delete 被删除的節點
資料範圍:
0<=連結清單節點值<=10000
0<=連結清單長度<=10000
示例1
輸入：
{2,5,1,9},5
傳回值：
{2,1,9}
說明：
給定你連結清單中值為 5 的第二個節點，那麼在調用了你的函數之後，該連結清單應變為 2 -> 1 -> 9
示例2
輸入：
{2,5,1,9},1
傳回值：
{2,5,9}
說明：
給定你連結清單中值為 1 的第三個節點，那麼在調用了你的函數之後，該連結清單應變為 2 -> 5 -> 9
思路 1
删除結點我這裡的思路是先進行一次周遊，周遊結束後要考慮三種情況：
- 1、沒找到：沒找到則進行相應處理，可抛出異常，可列印提示，也可傳回原連結清單，等等；
- 2、找到了，是第一個結點：則傳回連結清單的第二個結點作為頭結點；
- 3、找到了，不是第一個結點：則讓待删除結點的前驅，指向待删除結點的後繼，進而讓 Java 的垃圾回收器回收掉待删除結點，進而達到删除的目的，并且最終要傳回原連結清單的頭結點。
實作 1
public class JZ18删除連結清單的節點 {
public ListNode deleteNode(ListNode head, int val) {
if (head == null) return null;
ListNode temp = head;
ListNode pre = null;
while (temp != null && temp.val != val) {
pre = temp;
temp = temp.next;
}
//1 沒找到
if (temp == null) {
System.out.println("未找到此結點~");
return null;
}
//2 找到
// 2.1 是第一個結點
if (pre == null) return head.next;
// 2.2 非第一個結點
pre.next = temp.next;
return head;
}
} 思路 2
- 1 待删除結點：是第一個結點
-
2 待删除結點：是非第一個結點
2.1 待删除結點：未找到
2.2 待删除結點：找到
實作 2
public class JZ18删除連結清單的節點 {
public ListNode deleteNode(ListNode head, int val) {
if (head == null) return null;
ListNode temp = head;
//1 待删除結點：是第一個結點
if (temp.val == val) return temp.next;
//2 待删除結點：是非第一個結點
while (temp.next != null && temp.next.val != val) {
temp = temp.next;
}
//2.1 待删除結點：未找到
if (temp.next == null) return head;
//2.2 待删除結點：找到，為 temp.next
temp.next = temp.next.next;
return head;
}
}