给出一个头节点和待删除的节点,在O(1)的时间内删除该节点。(删除节点为X,前一个节点为i,后一个节点为j)
并没有想到思路,按平时的思路遍历到i节点,然后使i节点的next指向j节点。这样的思路也是O(n)的。

// 新思路:把节点j的内容复制到x,x指向j的下一个节点。但是有个问题,当x是尾指针的情况。
// 疑问:c/c++代码deleteNode函数中形参是指向指针的指针ListNode** node,java中怎么办呐?

package cn.wsw.offer;

import java.util.Scanner;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {

    // 此方法中返回值是ListNode而不是void的原因是:当节点只有一个,而且被删除,此时head节点应指向null。
    public static ListNode deleteNode(ListNode head, ListNode toDelete) {
        if (head == null || toDelete == null) {
            return null;
        }

        if (toDelete.next != null) { // 删除的节点不是尾节点
            toDelete.val = toDelete.next.val;
            toDelete.next = toDelete.next.next;
        } else if (head == toDelete) { //只有一个节点,要删除的节点既是头结点也是尾节点
            head = null;
        } else { // 有多个节点,删除尾节点
            ListNode t = head;
            while (t.next != toDelete) {
                t = t.next;
            }
            t.next = null;
        }
        return head;
    }

    public static void main(String[] args) {
        // 构造链表
        int[] array = {1,2,3,4,5};
        // int[] array = {1};
        ListNode head = new ListNode(array[0]), t = head;
        for (int i = 1; i < array.length; i++) {
            t.next = new ListNode(array[i]);
            t = t.next;
        }

        // 删除第k个节点 使toDelete指向要删除的节点
        int k = new Scanner(System.in).nextInt();
        ListNode toDelete = head;
        while (k > 1) {
            toDelete = toDelete.next;
            k--;
        }
        head = deleteNode(head, toDelete);

        // 遍历删除节点后的链表
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }

    }
}