剑指offer——删除链表的节点

/*
* 给定单向链表的头指针和一个结点指针,定义一个函数在0(1)时间删除该结点
*
* 【抖机灵】
* 正常删除链表节点都得给个头指针和要删除的结点,然后从头开始遍历寻找
* 但是要求时间复杂度是1,下面抖个机灵:
* 我们可以直接复制这个结点的下一个结点,然后再将这个结点的下一个结点删除。over
* 【注意】
* – 要删除的结点是尾结点
* – 没办法,NULL为系统中的特定的那块区域!!并无法复制,所以只能从头遍历,得到该结点的前序结点,删除。
* – 如果链表只有一个结点,即这个要删除的结点也是头节点,则,将nodeToBeDeleted置为空之后,还需把头节点置为空;
* – 由于Java子函数,只能是值传递,(所以不像C++,)必须返回新链表头节点,不然子函数就白调用了。
* 如果遍历找节点前一个节点然后删除的话需要O(n),我们可以分为删除不同位置的节点来考虑,
* 删除除尾节点外的其他节点,判断next是否为空,如果不为空,将next节点的值拷贝给当前节点,将当前节点的next指向next的next,next置为空;
* 删除只有一个节点的情况,直接置为空
* 在有多个节点的情况下删除尾节点,因为他没有next节点,无法复制,只能遍历找到前一个节点进行删除。
*
* 这种方法并不完美,无法确保要删除的节点在链表内,同时,需要的是要删除节点的指针
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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);
    }

}
0 条评论
发表一条评论