当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.237.Delete Node in a Linked List

LeetCode.237.Delete Node in a Linked List


题目描述

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 value 3, the linked list should become 1 -> 2 -> 4 after calling your function.


解题过程

删除单链表中指定值的结点,但是参数只有一个要删除的结点,没给链表的头结点。
开始我以为题出错了,想了半天都不知道怎么下手,对链表也有点儿生疏,已经有3年没写过有关链表的算法题了,上一次做还是14年底准备校招面试时。但我隐约记得如果给的是双链表的话,指定单独一个节点是可以删除的,因为有前向指针,现在是单链表就不知道怎么弄了。
琢磨了半天,才想到题意说的是只要在链表里删除指定的数据就行了,而且还提到删除的节点不是尾结点,就确定了肯定是通过挪数据的方式删除。

但我脑子比较笨,想到的方法是从要删除的节点开始挨个往前移数据:

class Solution {
    public void deleteNode(ListNode node) {
        while(node.next != null){
            node.val = node.next.val;
            if(node.next.next == null){ //倒数第二个结点
                node.next = null;//当前结点设为尾结点
                break;
            }
            node = node.next;
        }
    }
}

提交后看Discuss,才发现直接两部操作就行了:

public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

有人说这样会造成内存泄露,在c++里会,但java中不会,因为jvm有garbage collection,会自动释放无引用的变量。

不过确实不少人吐槽这道题出的不好,有误导嫌疑。

此外还要吐槽下,链表相关的题测试起来比较费劲,还好这道题我在LeetCode提供的Debug code in playground中找到一些附加代码,如下:

public class MainClass {
    //字符串"[1,2,3,4]"转为int数组
    public static int[] stringToIntegerArray(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
          return new int[0];
        }

        String[] parts = input.split(",");
        int[] output = new int[parts.length];
        for(int index = 0; index < parts.length; index++) {
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
        return output;
    }

    //字符串"[1,2,3,4]"转为ListNode链表
    public static ListNode stringToListNode(String input) {
        // Generate array from the input
        int[] nodeValues = stringToIntegerArray(input);

        // Now convert that list into linked list
        ListNode dummyRoot = new ListNode(0);//无数据的头结点
        ListNode ptr = dummyRoot;
        for(int item : nodeValues) {
            ptr.next = new ListNode(item);
            ptr = ptr.next;
        }
        return dummyRoot.next;
    }

    //ListNode链表转为字符串"[1,2,3,4]"
    public static String listNodeToString(ListNode node) {
        if (node == null) {
            return "[]";
        }

        String result = "";
        while (node != null) {
            result += Integer.toString(node.val) + ", ";
            node = node.next;
        }
        return "[" + result.substring(0, result.length() - 2) + "]";
    }
}

提供了字符串形式的数组和链表互相转换的方法,估计这几个方法在以后的链表题中都要用到,得好好存下来。


GitHub代码


上一篇 LeetCode.725.Split Linked List in Parts

下一篇 LeetCode.566.Reshape the Matrix

阅读
734
阅读预计3分钟
创建日期 2018-01-19
修改日期 2018-01-23
类别
百度推荐