【剑指offer】删除链表中的节点

给出一个头节点和待删除的节点，在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;
        }

    }
}