/*
* 给定单向链表的头指针和一个结点指针,定义一个函数在0(1)时间删除该结点
*
* 【抖机灵】
* 正常删除链表节点都得给个头指针和要删除的结点,然后从头开始遍历寻找
* 但是要求时间复杂度是1,下面抖个机灵:
* 我们可以直接复制这个结点的下一个结点,然后再将这个结点的下一个结点删除。over
* 【注意】
* - 要删除的结点是尾结点
* - 没办法,NULL为系统中的特定的那块区域!!并无法复制,所以只能从头遍历,得到该结点的前序结点,删除。
* - 如果链表只有一个结点,即这个要删除的结点也是头节点,则,将nodeToBeDeleted置为空之后,还需把头节点置为空;
* - 由于Java子函数,只能是值传递,(所以不像C++,)必须返回新链表头节点,不然子函数就白调用了。
* 如果遍历找节点前一个节点然后删除的话需要O(n),我们可以分为删除不同位置的节点来考虑,
* 删除除尾节点外的其他节点,判断next是否为空,如果不为空,将next节点的值拷贝给当前节点,将当前节点的next指向next的next,next置为空;
* 删除只有一个节点的情况,直接置为空
* 在有多个节点的情况下删除尾节点,因为他没有next节点,无法复制,只能遍历找到前一个节点进行删除。
*
* 这种方法并不完美,无法确保要删除的节点在链表内,同时,需要的是要删除节点的指针
*/
public class 删除链表的节点 { public static class Node{ int value; Node next; public Node(int data) { this.value = data; } } public static Node delnode(Node head,Node n) { if(head == null || n == null) return head; if(n.next != null) { Node temp = n.next; n.value = temp.value; n.next = temp.next; temp = null; }else if(head == n) { n = null; }else { Node temp = head; while(temp.next != n) { temp = temp.next; } n = null; temp.next = null; } return head; } public static void day(Node head) { while(head.next != null) { System.out.print(head.value); head = head.next; } System.out.println(head.value); } public static void main(String args[]) { Node head = new Node(1); head.next = new Node(2); Node middle = head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); Node last = head.next.next.next.next.next = new Node(6); head = delnode(head, head); // 删除头结点 day(head); head = delnode(head, last); // 删除尾结点 day(head); head = delnode(head, middle); // 删除中间结点 day(head); } }