Offer18_1（删除链表节点）

发表于 | 分类于 ，

题目：

　　给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。

思路：

　　正常删除链表节点的思路为找到待删除节点的前一个节点，使该节点的next指针指向待删除节点的下一个节点即可，但这种思路的时间复杂度为O(n)。与题目要求不符。根据
《剑指offer》的思路，可以将待删除节点的值修改为其下一个节点的值，然后将待删除节点的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
public ListNode deleteNode(ListNode head,ListNode pToBeDeleted) {
	if (head == null || pToBeDeleted == null) {
		return head;
	}
	// 删除的不是尾节点
	if (pToBeDeleted.next != null) {
		ListNode pNext = pToBeDeleted.next;
		pToBeDeleted.val = pNext.val;
		pToBeDeleted.next = pNext.next;
		pNext = null;
	// 删除的是尾节点并且原链表只有一个节点
	}else if (head == pToBeDeleted) {
		pToBeDeleted = null;
		head = null;
	// 删除的是尾节点并且原链表有多个节点
	}else {
		ListNode node = head;
		while(node.next != pToBeDeleted) {
			node = node.next;
		}
		node.next = null;
		pToBeDeleted = null;
	}
	return head;
}

复杂度分析：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。