LeetCode.237.Delete Node in a Linked List

---

题目描述

• 237 Delete Node in a Linked List
  https://leetcode.com/problems/delete-node-in-a-linked-list/description/

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-java / problems / _237_DeleteNodeInALinkedList /
  https://github.com/masikkk/algorithms/tree/master/leetcode/leetcode/_237_DeleteNodeInALinkedList

---