在 O(1) 时间内删除链表节点。在给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间内删除该节点。
链表节点与函数定义如下:
public class ListNode {
int val;
ListNode next = null;
}
void deleteNode(ListNode head, ListNode toBeDeleted);
- 功能测试(从有多个节点的链表的中间删除一个节点;从有多个节点的链表中删除头节点;从有多个节点的链表中删除尾节点)
- 特殊输入测试(指向链表头节点的为空指针;指向要删除节点的为空指针)
- 考查应聘者对链表的编程能力。
- 考查应聘者的创新思维能力。这道题要求应聘者打破常规的思维模式。 当我们想删除一个节点时,并不一定要删除一个节点本身,可以先把下一个节点的内容复制出来覆盖被删除节点的内容,然后把下一个节点删除。
- 考查应聘者思维的全面性。应聘者应该全面考虑删除的节点位于链表的尾部及输入的链表只有一个节点这种特殊情况。
核心:当我们想删除一个节点时,并不一定要删除一个节点本身,可以先把下一个节点的内容复制出来覆盖被删除节点的内容,然后把下一个节点删除。
- 如果该节点不是尾节点,那么可以直接将下一个节点的值赋给该节点,然后令该节点指向下下个节点,再删除下一个节点,时间复杂度为 O(1)。
- 如果该节点是尾节点,就需要先遍历链表,找到节点的前一个节点,然后让前一个节点指向 null,时间复杂度为 O(N)。
时间复杂度分析: 如果进行 N 次操作,那么需要操作节点的次数为 N-1+N=2N-1,其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数,N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。(2N-1)/N 约等于 2,因此该算法的平均时间复杂度为 O(1)。
没思路,新奇
/**
* 在O(1)时间内删除链表节点
*
* @Author rex
* 2018/7/23
*/
public class Solution1 {
/**
* 打破常规思维的链表删除方式
*
* @param head
* @param toBeDeleted
*/
public void deleteNode(ListNode head, ListNode toBeDeleted) {
// 两个指针否要考虑非法输入
if (head == null || toBeDeleted == null) {
return;
}
if (toBeDeleted.next != null) {
// 要删除的节点不是尾节点
ListNode next = toBeDeleted.next;
toBeDeleted.val = next.val;
toBeDeleted.next = next.next;
toBeDeleted.next = null;
} else {
// 要删除的节点是尾节点(只能遍历)
ListNode current = head;
while (current.next != toBeDeleted) {
current = current.next;
}
current.next = null;
}
}
}
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
- 功能测试(重复的节点位于链表的头部/中间/尾部;链表中没有重复的节点)
- 特殊输入测试(指向链表头结点的为null,链表中所有点都是重复的)
- 考查应聘者对链表的编程能力
- 考查应聘者思维的全面性。应聘者要全面考虑重复节点所处位置,以及删除重复节点之后的结果。
- 定义两个指针(preNode,node),一个用来指向不被删除的前一个节点,一个用来遍历链表
- 定义删除标志,如果前后两个值相等就需要删除,不等就不需要删除,改变preNode
- 在删除的时候需要连续删除,还要考虑preNode是或否存在,如果不存在它就是头指针
没思路
/**
* 删除链表重复的节点
* @Author rex
* 2018/7/23
*/
public class Solution2 {
/**
* 全面的删除
* @param pHead
* @return
*/
public ListNode deleteDuplication(ListNode pHead) {
// 防止非法输入
if (pHead == null || pHead.next == null) {
return pHead;
}
// 两个指针
ListNode preNode = null;
ListNode node = pHead;
while (node != null) {
ListNode next = node.next;
// 删除标志位
boolean needDeleted = false;
if (next != null && next.val == node.val) {
needDeleted = true;
}
if (!needDeleted) {
preNode = node;
node = node.next;
} else {
int value = node.val;
ListNode toBeDelete = node;
while (toBeDelete != null && toBeDelete.val == value) {
next = toBeDelete.next;
toBeDelete = next;
// 考虑头指针是否存在
if (preNode == null) {
pHead = next;
} else {
preNode.next = next;
}
node = next;
}
}
}
return pHead;
}
}