【算法】解题总结：剑指Offer 73 翻转单词序列、剑指Offer 18 删除链表的节点

本文主要是介绍【算法】解题总结：剑指Offer 73 翻转单词序列、剑指Offer 18 删除链表的节点，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

JZ73 翻转单词序列

（中等）

题目

描述
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

示例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、没找到：没找到则进行相应处理，可抛出异常，可打印提示，也可返回原链表，等等；
• 2、找到了，是第一个结点：则返回链表的第二个结点作为头结点；
• 3、找到了，不是第一个结点：则让待删除结点的前驱，指向待删除结点的后继，从而让 Java 的垃圾回收器回收掉待删除结点，从而达到删除的目的，并且最终要返回原链表的头结点。

实现

public class JZ18删除链表的节点 {
    public ListNode deleteNode(ListNode head, int val) {
        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;
    }
}

这篇关于【算法】解题总结：剑指Offer 73 翻转单词序列、剑指Offer 18 删除链表的节点的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！