By

文章目录
  1. 1. 题目
  2. 2. 解题
  3. 3. 代码

题目

在O(1)时间内删除一个单链表上指定的节点

解题

这题主要是需要O(1)的复杂度，我们之前一般删除节点的方法都是找到要删除节点p，然后p.parent.next=p.next就可以了，但是那个复杂度是O(n)

不过这里有一种我称为狸猫换太子的方法来解决这个问题

1->2->3->4->5
 假如现在要删除p.data=3
 首先将p.data=p.next.data
 1->2->4->4->5
 然后将p.next删除
 1->2->4->5

 如果是尾节点  需要重新遍历

思路很精妙，就是将p.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
/**
 * <pre>
 * 1->2->3->4->5
 * 假如现在要删除p.data=3
 * 首先将p.data=p.next.data
 * 1->2->4->4->5
 * 然后将p.next删除
 * 1->2->4->5
 * 
 * 如果是尾节点  需要重新遍历
 * 还有 如果是p==head  则直接得置空  但是在java中这个操作不是很好做。所以。。。
 * </pre>
 * @param head
 * @param dNode
 */
public static void deleteNodeInO1(Link head,Link p)
{
	if(p==null)
		return;
	
	if(p.next==null)
	{
		//表示尾部节点
		Link q=head;
		while(q.next!=p)
			q=q.next;//找到尾节点的前一个节点
		q.next=null;//进行删除
	}else{
		p.data=p.next.data;
		p.next=p.next.next;
	}
}

public static void print(Link head)
{
	Link p=head;
	while(p!=null)
	{
		System.out.print(p.data);
		p=p.next;
	}
	System.out.println();
}

static class Link{
	public int data;
	public Link next;
	public Link(int data)
	{
		this.data=data;
	}
}

只是要删除节点是头部或者尾部的时候需要额外考虑，按遍历的方法删除即可

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权

文章目录
  1. 1. 题目
  2. 2. 解题
  3. 3. 代码